Codeforces Round #670 (Div. 2) A. Subset Mex (贪心)

题意:给你一长度为\(n\)的序列,将其分为两个集合,求两个集合中未出现的最小元素的最大值,
题解:用桶存一下每个元素的个数,两次枚举\([1,100]\),找出两个最小值即可.

代码:

int t;

int n;

int a[N];

map<int,int> mp;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

    	cin>>n;

    	mp.clear();

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

    		cin>>a[i];

    		mp[a[i]]++;

    	}

    	int tmp1,tmp2;

    	for(int i=0;i<=100;++i){

    		if(mp[i]) mp[i]--;

    		else{

    			tmp1=i;

    			break;

    		}

    	}

    	for(int i=0;i<=100;++i){

    		if(!mp[i]){

    			tmp2=i;

    			break;

    		}

    	}

    	cout<<tmp1+tmp2<<endl;

    }

    return 0;

}

巴特西

Codeforces Round #670 (Div. 2) A. Subset Mex (贪心)

最新文章

热门文章