Решение задачи Боксёры с Codeforces

С пояснением   Просмотров: 62

Есть n боксёров, вес i-го равен ai. Каждый из них перед соревнованием может изменить свой вес не более чем на 1 (вес не может стать равным нулю, то есть должен остаться положительным). Вес — это всегда целое число.

Необходимо выбрать наибольшую по количеству человек такую команду боксёров, что все веса боксёров в ней — различны.

Напишите программу, которая для заданных текущих значений ai найдет максимальное возможное количество боксёров в команде.

Возможно, что после какого-то изменения вес какого-то боксера станет 150001 (но не больше).

Код 

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	int lst = a[0] + 2;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int cur = -1;
		for (int dx = 1; dx >= -1; --dx) {
			if (a[i] + dx > 0 && a[i] + dx < lst) {
				cur = a[i] + dx;
				break;
			}
		}
		if (cur == -1) continue;
		++ans;
		lst = cur;
	}
	cout << ans << endl;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Пусть lst равно последнему весу боксера, взятого в команду. Изначально lst=∞. Отсортируем всех боксеров в порядке невозрастания их весов и пройдем по всем боксерам слева направо. Если текущий боксер имеет вес w, то давайте попробуем взять его с весом w+1 (мы можем сделать это, если w+1



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта