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

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

Есть 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;
}