Codeforces 1684 E. MEX vs DIFF

题意

给你n个非负整数的数列a，你可以进行K次操作，每次操作可以将任意位置的数数更改成任意一个非负整数，求操作以后，DIFF(a)-MEX（a）的最小值；DIFF代表数组中数的种类。MEX代表数组中未出现的最小自然数。

提示

1. 显然 DIFF(a)-MEX（a）最小，DIFF(a)越小越好，MEX(a)越大越好

2. 假如 DIFF 降低，同时 MEX 提升，这样操作是不亏的，因此我们只需要提升MEX即可，贪心的的构造0-x，x为k次修改，能构建到mex的最大的数列a状态。

3. 在原始a中，0-x中空缺的值即为需要填充个数的值，我们只需要贪心，先填入出现次数少的>x的值，以降低它的DIFF，即MEX固定了，再降低其DIFF

代码

#include

using namespace std;
int a[100005], cnt[100005];
map<int, int> mp;
struct node {
    int x, y;
} op[100005];

void run() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i <= n; i++) {
        cnt[i] = 0;
    }
    set<int> s;
    mp.clear();
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < n)cnt[a[i]]++;
        s.insert(a[i]);
        mp[a[i]]++;
    }

    int res = 0, flag = n;
    for (int i = 0; i < n; i++) {
        if (cnt[i] == 0)res++;
        if (res > k) {
            flag = i;
            break;
        }
    }
    int st = 0;
    for (auto [x, y]: mp) {
        if (x >= flag)op[++st] = {x, y};
    }
    sort(op + 1, op + 1 + st, [&](const node &x, const node &y) { return x.y < y.y; });
    int sum = 0;
    int ree = min(res, k);
    for (int i = 1; i <= st; i++) {
        ree -= op[i].y;
        if (ree >= 0)sum++;
        else break;
    }
    cout << min(res, k) - sum + int(s.size()) - flag << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--)
        run();
    return 0;
}