Codeforces 1406A - Subset Mex (水題)

題目大意：

定義 mex: 這集合裡面缺少的最小負整數。
如 \(mex( \{ 1,4,0,2,2,1 \} ) = 3\)，缺少 \(3\)
如 \(mex(\{3,2,3,1,3,0,0\}) = 4\)，缺少 \(4\)

給你一組數列，要把它拆成 A , B 兩個子集，如果此數列裡面有重複的數字時需要平均分配給 A , B。試問如何讓 \(mex(a) + mex(b) \) 最大？

分析：

依序把數列讀入，之後排序，再透過 a , b 兩個變數紀錄這數列裡面缺少的最小與次小的負整數就是答案。

為甚麼可以這樣做？

由於 mex 的定義，是集合裡面缺少的最小負整數，而再根據題目拆子集的要求只要有重複的就要分配給 a,b 兩個集合。

然後我們來舉個例:

• \( \{ 0,1,2,3 \} \)

  \(A = \{1,2,3 \} , mex(A)=4 \)
  \(B = \{\} , mex(B)=0 \)

• \(\{0,0,1,1,2,4\}\)

  \(A = \{0,1,2,4\} , mex(A) = 3 \)
  \(B = \{0,1\} , mex(B) = 2 \)
  這裡的 4 放在 A 或 B 都沒關係，不影響

得出結論

數列中，如果此數列中沒有重複的最小整數，那最小整數就會是 \(mex(B)\)，A 則是排序中第一個缺失的最小整數。

於是我們排序好，直接用一個 for，只要根據數字順序判斷這數列哪裡數字缺失就是 A 的位置，而 B 就是沒有重複的最小整數。

參考連結

Codeforces Round #670 (Div. 2) 深夜掉分（A - C题补题）

心得

其實這場比賽我一題都沒有解出來www，實力不好啊！也不太會分配時間，這點我還需要再學習。然後這題有個很大的重點讓當時的我沒有解出來，就是我看不懂他的英文 ，導致我在讀懂題目就花了 30 分鐘卻還沒有讀懂題目，浪費掉了許多時間。英文能力真的很重要，一定要學好。

等我 ICPC 2020 taipei 比完後我一定要來好好惡補我的英文能力，演算法也要好嗎= = ~。我還有好多事情要努力要學習，好希望自己的學習能力能夠好點。

感謝 RioTian 大神分享程式碼讓我可以看到這種程式解法，我知道中文題目後我沒有想到這種解法，而且這種解法更有效率更好懂！讓我學習了一課，謝謝大神讓我能夠往前成長一步。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 110
using namespace std;
int t , n , num[MAXN] ={} ;

int main()
{
//#ifdef LOCAL
//    freopen("in1.txt" ,"r" , stdin ) ;
//#endif // LOCAL

    cin >> t ;
    while(t--){
        cin >> n ;
        for(int i = 0 ; i < n ; i++)
            cin >> num[i] ;
        sort(num,num+n);

        int a=0 , b = 0 ;
        for(int i = 0 ; i < n ; i++){
            if(num[i] == a ) a++;
            else if (num[i] == b ) b++ ;
        }
        cout << a + b << '\n' ;
    }

    return 0;
}