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.

题意概述

有$N$只猫戴着帽子，每一顶帽子都有一种颜色。第$i$只猫看到了$a_i$种颜色的帽子（它看不到自己的帽子），问是否存在一种不矛盾的颜色分配方案。

数据范围：$2 \le N \le 10^5, \ 1 \le a_i \le N-1$。

算法分析

首先可以发现所有数中最大值$mx$和最小值$mn$之差一定不大于$1$。证明如下：

定义$c_i$为第$i$只猫帽子颜色出现的次数。设$i \neq j$。如果$c_i=1 \land c_j=1$，那么$a_i=a_j$；如果$c_i=1 \land c_j \gt 1$，那么$a_i+1=a_j$；如果$c_i \gt 1 \land c_j=1$，那么$a_i=a_j+1$；如果$c_i \gt 1 \land c_j \gt 1$，那么$a_i=a_j$。

由此得证。

如果$mx=mn$，那么有两种情况：

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

如果$mx \gt mn$，令$p$为所有数中等于$mn$的数的个数。根据上面的证明，若$a_i=mn$则$c_i=1$，若$a_i=mx$则$c_i \gt 1$。易知$p$等于满足$c_i=1$的$i$的个数，即唯一出现的颜色的个数；而$mx$等于所有颜色的个数。因此，只需要满足$mx \gt p \land n - p \ge 2(mx-p)$即可。

代码

#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;
}