题意

给你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<bits/stdc++.h>

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;

}

巴特西

Codeforces 1684 E. MEX vs DIFF

题意

提示

代码

最新文章

热门文章