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

题目

给定一组 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

输入样例：

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

思路

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

C++代码

#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;
}