Description
有n个人，每个人都戴着一顶帽子。当然，帽子有不同的颜色。现在，每个人都告诉你，他看到的所有其他人的帽子共有多少种颜色，请问你有没有符合所有人的描述的情况。
Solution
先是一个显然的性质，数列的最大值与最小值之差一定小于等于2！！！（丢了20pts）
首先，我们将序列排序。考虑看到颜色数最多的那个人，设他看到了k种颜色，那么，总共只可能有k或者k+1种可能的颜色。
1、总共有k种颜色
那么对于b个\(a_i<k\)的人，他们一定要被安排一种独一无二的颜色，而对于剩下\(种k-b种\)颜色每种颜色至少要被安排2个人，所以判断\(n-b\)和\(k-b\)的关系。
2、总共有\(k+1\)种颜色
那么只能每人分配一种不同的颜色
Hint
\(2\leqslant n\leqslant 10^5\)
\(1\leqslant a_i \leqslant n - 1\)
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 100000 + 10;
int n, a[maxn];
bool cmp(int a, int b) {
return a > b;
}
//k
inline int solve1() {
int b = 0, k = a[1];
for(int i = 1;i <= n;i ++) if(a[i] < a[1]) b ++;
if(b > k) return 0;
if(b == k) return 0;
int tmp = k - b;
int now = n - b;
if(now >= 2 * tmp) return 1;
else return 0;
}
inline int solve2() {
int b = 0, k = a[1];
for(int i = 1;i <= n;i ++) if(a[i] == a[1]) b ++;
if(b > k + 1) return 0;
if(b == k + 1) {
if(k + 1 == n) return 1;
else return 0;
}
int tmp = k + 1 - b;
int now = n - b;
if(now) return 0;
else return 1;
}
int main() {
scanf("%d", &n);
for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
sort(a + 1,a + n + 1,cmp);
if(a[1] - a[n] >= 2) {
puts("No");
return 0;
}
if(solve1()) {
puts("Yes");
}
else {
if(solve2()) {
puts("Yes");
}
else puts("No");
}
return 0;
}