题目描述
给定一组 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 两个子集。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行一个结果,表示 mex(A)+mex(B) 的最大值。
数据范围
1≤T≤100,
1≤n≤100,
0≤ai≤100
输入样例:
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
样例解释
在第一个测试用例中,A={0,1,2},B={0,1,5} 是一个可能的选择。
在第二个测试用例中,A={0,1,2},B=∅ 是一个可能的选择。
在第三个测试用例中,A={0,1,2},B={0} 是一个可能的选择。
在第四个测试用例中,A={1,3,5},B={2,4,6} 是一个可能的选择。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
int n;
int r[N];
int mex()
{
for (int i = 0; i < N; i++) //遍历
{
if (!r[i])
return i; //r[i] == 0时,返回mex值i
else
r[i]--; //mex值往后减1,继续遍历,直到满足if条件
}
return -1;
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n;
memset(r, 0, sizeof r); //数组清零
while (n--)
{
int x;
cin >> x;
r[x]++; //+1表示mex值,因为mex至少比当前读入的数大1
}
cout << mex() + mex() << endl;
}
return 0;
}