思路

用一个类似桶的结构,存储每个体重存在的数量

然后进行贪心即可

每个体重有用的人数最多为三人

并且能够加入 $Ans$ 与且仅与上一个体重的人和下一个体重的人有关

那我们只需从小到大进行贪心,注意有个细节:要先判断当前位置的上一个(使其+1),然后再是当前体重(不变),最后是下一个体重(使其-1)【与贪心扫描顺序相同】

标程

#include <bits/stdc++.h>
using namespace std;

int cnt[200000 + 10] ,n  ,MAXN ,Ans;

int main() {
	scanf("%d" ,&n);
	for(int i = 1;i <= n;i++) {
		int temp;
		scanf("%d" ,&temp);
		cnt[temp]++;
		MAXN = max(MAXN , temp);
	}
	for(int i = 1;i <= MAXN + 1;i++) {
		if(cnt[i - 1]) {
			cnt[i - 1]--;
			Ans++;
		}
		else if(cnt[i]) {
			cnt[i]--;
			Ans++;
		}
		else if(cnt[i + 1]) {
			cnt[i + 1]--;
			Ans++;
		}
	}
	printf("%d" ,Ans);
	return 0;
}