题目描述
给定一组 n 个整数的集合 a1,a2,…,an(可能存在相同元素)。
请你将该集合分为两个子集 A 和 B(子集可以为空,也可以包含相同元素)。
要求 mex(A)+mex(B) 的值尽可能大。
一个集合的 mex 值等于集合中不存在的最小非负整数的值,例如:
mex({1,4,0,2,2,1})=3
mex({3,3,2,1,3,0,0})=4
mex(∅)=0
如果集合中的任意整数 x 均满足 x 在该集合中的出现次数等于 x 在 A 中出现的次数与 x 在 B 中出现的次数之和,则我们认为该集合被分成了 A 和 B 两个子集。
样例
输入样例:
4
6
0 2 1 5 0 1
3
0 1 2
4
0 2 0 1
6
1 2 3 4 5 6
输出样例:
5
3
4
0
(暴力枚举) O(n)
从小到大搜索最小的且未出现的数字,搜索两遍,注意第一次搜索的时候将所有已经搜索过的数字个数减1
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
int num[110];
int main(void){
int T;
cin>>T;
while(T--){
int n;
scanf("%d",&n);
memset(num,0,sizeof(num));
for(int i=0;i<n;i++){
int t;
scanf("%d",&t);
num[t]++;
}
int all=0;
for(int i=0;i<=100;i++){
if(num[i]>0){
num[i]--;
}
else {
all+=i;
break;
}
}
for(int i=0;i<=100;i++){
if(num[i]>0){
num[i]--;
}
else {
all+=i;
break;
}
}
printf("%d\n",all);
}
return 0;
}
哥哥,好帅,我好爱
tql orz