题目描述
给定一组 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} 是一个可能的选择。
算法1
(模拟) $O(n)$
时间复杂度
参考文献
python3 代码
import collections
T = int(input())
for _ in range(T):
n = int(input())
nums = [int(x) for x in input().split()]
x_f = [0 for _ in range(102)]
for x in nums:
x_f[x] += 1
a = -1
for x in range(0, 102):
if x_f[x] == 0:
a = x
break
else:
x_f[x] -= 1
b = -1
for x in range(0, 102):
if x_f[x] == 0:
b = x
break
print(a + b)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T; cin >> T;
while(T --)
{
int n; cin >> n;
int x_f[102];
memset(x_f, 0, sizeof(x_f));
while (n -- )
{
int x; cin >> x;
x_f[x] ++;
}
int a = -1;
for (int x = 0; x < 102; x ++)
{
if (x_f[x] > 0)
{
x_f[x] --;
}
else
{
a = x;
break;
}
}
int b = -1;
for (int x = 0; x < 102; x ++)
{
if (x_f[x] == 0)
{
b = x;
break;
}
}
cout << a + b << endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla