題目大意：

給定n和n個數，每個數a[i]代表除了i外序列中顏色不同的數的個數，問能否構造出來這個數列。

?

比較簡單，首先先求出來a數列的最大值Max，

如果有數小于Max-1，那么顯然是不存在的

接下來就是有m個數等于Max-1，n-m個數等于Max

那么可以知道m個數中每個數肯定是有且只有一種顏色

所以m<Max，剩下的必須至少有2個，所以條件就是m<Max && m + 2*（Max-m) <= n

特殊情況：所有數都等于Max，這時候有2種情況，一種是每個數都是不同的，一種是2*Max <= n，判斷一下就好

?

#include <iostream> #include <cstring> #include <cstdio> #include <map> using namespace std; int n; int a[1000000]; map<int, int>M; int main() {cin>>n;for(int i = 0; i < n; i++) cin>>a[i];int Max = 0, t = 0;for(int i = 0; i < n; i++){if(!M[a[i]]) { M[a[i]] = 1; t++; Max = max(Max, a[i]); }}for(int i = 0; i < n; i++) if(a[i] < Max-1) { cout<<"No"<<endl; return 0; }if(t > 2) { cout<<"No"<<endl; }else {int m = 0;for(int i = 0; i < n; i++) if(a[i] == Max-1) m++;if(m == 0) {if(2*(Max-m) <= n) cout<<"Yes"<<endl;else if(Max == n-1) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;}if(m < Max && (m + 2*(Max-m) <= n)) cout<<"Yes"<<endl;else cout<<"No"<<endl;} }

?

轉載于:https://www.cnblogs.com/Saurus/p/7048324.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的AGC016B Colorful Hats（构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。