题目

Solution

这题做着挺顺，我就按我的心路历程讲下去好了
先请大家搞清楚颜色数和颜色的个数，不然看下去会觉得我讲得很奇怪
假设 m x = m a x { a i } , m n = m i n { a i } mx=max\lbrace a_i\rbrace,mn=min\lbrace a_i\rbrace mx=max{ai​},mn=min{ai​}
首先，能发现 m x mx mx与 m n mn mn最多相差 1 1 1
我脑子中首先想到的就是要定一个基准，又立刻把基准定为了总颜色数 c o l col col
容易想到 c o l col col与 m x mx mx最多相差 1 1 1
那就可以分类讨论：
① c o l = m x + 1 ①col=mx+1 ①col=mx+1，那么 m n = m x mn=mx mn=mx，所有 a i a_i ai​相等
此时要么所有帽子的颜色不同： m n = n − 1 mn=n-1 mn=n−1，
要么每种颜色的个数 &gt; 1 &gt;1 >1，因为这样的话这种颜色少了一个也不会影响总颜色数，所以 m n &lt; = n / 2 mn&lt;=n/2 mn<=n/2
② c o l = m x ②col=mx ②col=mx，那么 m n = c o l − 1 mn=col-1 mn=col−1，那 a i a_i ai​中一定有 m m m个 m n mn mn（ m m m是设的）和 n − m n-m n−m个 m x mx mx
很明显，所有等于 m n mn mn的 a i a_i ai​所对应的颜色的个数都是 1 1 1（删掉这个点就少了一种颜色，那这种颜色显然只有一个），那么 m m m个颜色已经确定，剩下的那些点的颜色数可以参考 ① ① ①，一定是 &lt; = ( n − m ) / 2 &lt;=(n-m)/2 <=(n−m)/2的，所以 m + 1 &lt; = c o l &lt; = m + ( n − m ) / 2 m+1&lt;=col&lt;=m+(n-m)/2 m+1<=col<=m+(n−m)/2

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100002;
int n,i,a[N],col,m;
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
int main(){
	n=rd();
	for (i=1;i<=n;i++) a[i]=rd();
	sort(a+1,a+n+1);//不要问我为什么要排序，我懒，懒得打for循环
	if (a[1]==a[n]) return puts(a[1]<=n/2 || a[1]==n-1?"Yes":"No"),0;
	if (a[n]-a[1]>1) return puts("No"),0;
	col=a[n];
	for (i=1;a[i]==a[1];i++);
	m=i-1;
	puts(m+1<=col && col<=(n-m)/2+m?"Yes":"No");
}