题解：AT_agc016_b [AGC016B] Colorful Hats

· · 题解

题意

有 n 只猫，每只猫有一顶一种颜色的帽子。现在给出每只猫能看到的其它猫的帽子的颜色种数，试问有没有一种构造方案能使它满足。

思路

首先观察样例，很容易将输入分成两类去判断。第一种是所有猫看到的帽子颜色的数量全部相等，另一种是不相等。

先考虑第一种：此时发现，如果所有猫能看到的都等于 n-1 是可以的。接着继续考虑不等于 n-1 的情况。在这种情况中，一定是有一种颜色的帽子的个数大于等于 2 的。我们更进一步去考虑，如果在这种情况下有一种颜色的帽子的数量为 1，那么戴着这个帽子的猫看到的颜色数量一定不等于那些帽子颜色出现多次的猫看到的颜色数量。于是是不存在帽子的颜色只出现一次的。而一种颜色的出现次数大于等于 2 的时候，再多一些其实对答案并无影响，因为无论哪只猫都一定能看到这个颜色。于是我们只需要判断这个数是不是等于 n-1 或小于等于 \frac{n}{2} 即可。

接下来考虑第二种情况：不难得出如果看到颜色最多的猫看到的颜色比看到颜色最少的猫看到的颜色多超过一种，那么是不满足的。因为一只猫的帽子只有一种颜色，所以每只猫最多只会看不到自己的帽子的颜色，不可能大于 1。并且那些看到的颜色数少的那一类猫，他们的帽子颜色出现次数等于 1。此时可以得到第一个判断：看到的颜色数少的猫的个数一定小于等于他们看到的颜色数。因为后面看的颜色数多的猫的帽子的颜色至少一种，而看的少的的颜色数等于看的少的猫的数量，如果这个数大于他们所能看到的颜色数加一那么就一定不能构造出来了。并且由于所有看的颜色数多的猫的帽子颜色的出现次数一定大于等于 2，我们可以得到第二个判断：看的颜色数少的猫的个数加看的颜色数多的猫的个数除以二向下取整一定大于等于看的颜色数多的猫看到的颜色数。因为最多就这么多种颜色，如果看的多的猫看的比这个还多就一定构造不出来了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    if(a[1]==a[n]&&(a[1]==n-1||a[1]<=n/2)){
        cout<<"Yes";
        return 0;
    }
    else if(a[n]-a[1]==1){
        int tmp=1;
        for(tmp;a[tmp]==a[tmp+1];tmp++){}//找到两种猫的分界处
        if((n-tmp)/2+tmp>=a[n]&&tmp<=a[1]){//满足条件
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

AC 记录。