【每日一题】AcWing 3705.子集mex值

本文最后更新于:2021年6月22日 晚上

题目

给定一组 n 个整数的集合 a1,a2,…,an(可能存在相同元素)。

请你将该集合分为两个子集 A 和 B(子集可以为空,也可以包含相同元素)。

要求 mex(A)+mex(B) 的值尽可能大。

一个集合的 mexmex 值等于集合中不存在的最小非负整数的值,例如:

  • 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。

第二行包含 nn 个整数 a1,a2,…,an。

输出格式

每组数据输出一行一个结果,表示 mex(A)+mex(B)的最大值。

数据范围

1≤T≤100,
1≤n≤100,
0≤ai≤100

输入样例:

1
2
3
4
5
6
7
8
9
4
6
0 2 1 5 0 1
3
0 1 2
4
0 2 0 1
6
1 2 3 4 5 6

输出样例:

1
2
3
4
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} 是一个可能的选择。

思路

贪心思想,因为题目没有要求具体的分割方法,所以越小的肯定是最优的结果,先存入所有数出现的次数,然后从0开始枚举找到最小的数即可。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=110;

int a[N];

int calc()
{
for(int i=0;i<N;i++)
{
if(!a[i]) return i;
else a[i]--;
}
return -1;
}

int main()
{
int t;
cin>>t;
while(t--)
{
memset(a, 0 ,sizeof(a));
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a[x]++;
}
cout<<calc()+calc()<<endl;
}
return 0;
}