題意：有$N$只貓，每只貓帶著某種顏色的帽子，給出每只貓能看到（即其他$N-1$只貓）的顏色種數(shù)$a[i]$，問是否可以構(gòu)造出合法序列。

首先有一個顯而易見的結(jié)論，及最大值和最小值相差不超過1

我們考慮最小值的形成，是因為這只貓看不見自己頭上的帽子所以會少1

這樣又得到了一個結(jié)論，看到顏色數(shù)目為最小值的貓頭上顏色唯一，其他貓頭上的顏色至少為2

根據(jù)這兩個結(jié)論，我們就可以做這道題

代碼：

1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int n,num,maxn,minn; 5 int a[100001]; 6 int main() 7 { 8 cin>>n; 9 for(int i=1;i<=n;i++) cin>>a[i]; 10 sort(a+1,a+1+n); 11 minn=a[1],maxn=a[n]; 12 if(minn<maxn-1||maxn>=n) {cout<<"No";return 0;} 13 if(maxn==minn) 14 { 15 if(minn+1==n) cout<<"Yes"; 16 else 17 { 18 if(minn*2>n) cout<<"No"; 19 else cout<<"Yes"; 20 } 21 return 0; 22 } 23 for(int i=1;i<=n;i++) if(a[i]==minn) num++; 24 n-=num; maxn-=num; 25 if(minn<num) cout<<"No"; 26 else if(maxn*2>n) cout<<"No"; 27 else cout<<"Yes"; 28 return 0; 29 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Slrslr/p/9713374.html

總結(jié)

以上是生活随笔為你收集整理的[AGC016B]Colorful Hats的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。