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

  • ACM
  • 算法
  • 贪心
  • acwing
    abbrlink: 4a55d7b7
    date: 2021-06-22 16:06:59

题目

给定一组 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. 4
  2. 6
  3. 0 2 1 5 0 1
  4. 3
  5. 0 1 2
  6. 4
  7. 0 2 0 1
  8. 6
  9. 1 2 3 4 5 6

输出样例：

  1. 5
  2. 3
  3. 4
  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. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  5. using namespace std;
  7. const int N=110;
  9. int a[N];
  11. int calc()
  12. {
  13.     for(int i=0;i<N;i++)
  14.     {
  15.         if(!a[i])   return i;
  16.         else a[i]--;
  17.     }
  18.     return -1;
  19. }
  21. int main()
  22. {
  23.     int t;
  24.     cin>>t;
  25.     while(t--)
  26.     {
  27.         memset(a, 0 ,sizeof(a));
  28.         int n;
  29.         cin>>n;
  30.         for(int i=0;i<n;i++)
  31.         {
  32.             int x;
  33.             cin>>x;
  34.             a[x]++;   
  35.         }
  36.         cout<<calc()+calc()<<endl;
  37.     }
  38.     return 0;
  39. }