题解：AT_agc016_b [AGC016B] Colorful Hats

Thomas0218 · 2026-01-23 11:11:33 · 题解

我们设只有一顶的帽子有 s 种，数量多于一个的有 t 种。我们可知 s+2t\leq n 是有解的必要条件。

做如下分类讨论：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5; int n, a[N]; map <int,int> mp;
int main() {
    scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); mp[a[i]]++; }
    if(mp.size() > 2) return printf("No\n"), 0;
    int mn = n, mx = 0; for(int i = 1; i <= n; i++) mn = min(mn, a[i]), mx = max(mx, a[i]);
    if(mx - mn > 1) return printf("No\n"), 0;
    if(mn == mx && mx == n - 1) return printf("Yes\n"), 0;
    else if(mn == mx) { if(2 * mx <= n) printf("Yes\n"); else printf("No\n"); }
    else {
        int s = mp[mn], t = mx - s;
        if(s + 2 * t <= n && t > 0) printf("Yes\n"); else printf("No\n");
    }
    return 0;
}