# Colorful Hats

## 题目描述

There are $N$ cats. We number them from $1$ through $N$.
Each of the cats wears a hat. Cat $i$ says: “there are exactly $a_i$ different colors among the $N-1$ hats worn by the cats except me.”
Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.

## 算法分析

1. 对于所有的$i$均有$c_i=1$。此时$n=mx+1$；
2. 对于所有的$i$均有$c_i \gt 1$。此时$n \ge 2mx$。

## 代码

#include <iostream>
using namespace std;
int n, a[100001], ma, mi, p;
int main()
{
cin >> n;
mi = 1e9;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
ma = max(ma, a[i]);
mi = min(mi, a[i]);
}
if (ma - mi > 1) {
cout << "No" << endl;
} else {
if (ma == mi) {
if (ma + 1 != n && ma << 1 > n) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
} else {
for (int i = 1; i <= n; ++i) {
if (a[i] == mi) p++;
}
if (ma <= p || ma - p << 1 > n - p) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
}
}
return 0;
}


418 I'm a teapot