AGC016B Colorful Hats（构造）

题目大意：

给定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[];

map<int, int>M;

int main()

{

    cin>>n;

    for(int i = ; i < n; i++) cin>>a[i];

    int Max = , t = ;

    for(int i = ; i < n; i++){

        if(!M[a[i]]) { M[a[i]] = ; t++; Max = max(Max, a[i]); }

    }

    for(int i = ; i < n; i++) if(a[i] < Max-) { cout<<"No"<<endl; return ; }

    if(t > ) { cout<<"No"<<endl; }

    else {

        int m = ;

        for(int i = ; i < n; i++) if(a[i] == Max-) m++;

        if(m == ) {

            if(*(Max-m) <= n) cout<<"Yes"<<endl;

            else if(Max == n-) cout<<"Yes"<<endl;

            else cout<<"No"<<endl;

            return ;

        }

        if(m < Max && (m + *(Max-m) <= n)) cout<<"Yes"<<endl;

        else cout<<"No"<<endl;

    }

}

巴特西

AGC016B Colorful Hats（构造）

最新文章

热门文章