[貪心] aw3705. 子集mex值(貪心+模拟+模闆題)

文章目錄

• • 1. 題目來源
  • 2. 題目解析

1. 題目來源

連結：3705. 子集mex值

2. 題目解析

貪心+模拟。

假設有兩個 0，則這兩個 0 一定要不要放到一個數組中，不然将導緻另一個數組的

mex()

是 0。

那麼就盡量讓兩個集合都能連續出現數字，可以先給第一個集合盡量連續的分連續的數，直至分不了，得到它的

mex()

值，其中用到的每個數都減 1。然後給第二個集合盡量分連續的數就行了。

看代碼會很容易懂！證明和代碼實作兩者有點差別，在此上面的根本算不上嚴格證明！請注意！

時間複雜度： O ( n ) O(n) O(n)

空間複雜度： O ( n ) O(n) O(n)

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int n, m;
int a[N];

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

int main() {
    int T;
    scanf("%d", &T);
    
    while (T -- ) {
        scanf("%d", &n);
        memset(a, 0, sizeof a);
        
        for (int i = 0; i < n; i ++ ) {
            int x;
            scanf("%d", &x);
            a[x] ++ ;
        }
        
        printf("%d\n", mex() + mex());
    }
    
    return 0;
}