CF1684E. MEX vs DIFF 题解

lingfunny · 2022-06-06 11:15:15 · 题解

1684E. MEX vs DIFF *2100

题意：给 n 个数，最多可以改 k 个数，请最小化 \operatorname{DIFF}-\operatorname{MEX}。

首先观察性质，然后做。

1. 性质 1：k 次修改一定会用完。证明：因为用了不可能使得答案更劣。
2. 性质 2：要修改，一定会修改成 \operatorname{MEX}。证明：修改成其它的没有意义，就算之后会用到，那先用到也没差。因为没有 \operatorname{MEX} 这个数，所以一定要有人顶替它。
3. 由上面两个性质，可以得出最后的 \operatorname{MEX} 是固定的，先写个 for 跑出 \operatorname{MEX}。现在只需要 \operatorname{DIFF} 最小即可。
4. 贪心。因为你会改的数是 k 个，要让 \operatorname{DIFF} 减少，只能选择让 \ge \operatorname{MEX} 的数变成 <\operatorname{MEX} 的。按照每个数出现的次数贪心即可。

// Problem: E. MEX vs DIFF
// From: Codeforces - Codeforces Round #792 (Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/1684/E
// Time: 2022-06-05 10:27
// Author: lingfunny

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn = 1e5+10;

int n, k, a[mxn], b[mxn], tot;
int MEX, lft, diff, cgb;

// k 次修改一定要全用完
// 要修改，一定会修改成 MEX
// 问题就是修改哪些数变成 MEX
// 可以找到不管修改谁 ，修改 k 次后，MEX 最大为多少
// 看起来答案的 MEX 不变，于是看怎么删能让 diff 最少
struct node {
    int val, cnt;
    inline bool operator < (const node &rhs) const {
        int fu = val < MEX, fv = rhs.val < MEX;
        if(fu != fv) return fu > fv;
        return cnt > rhs.cnt;
    }
};
priority_queue <node> Q;

inline void solve() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%d", a+i);
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; ++i) b[i] = a[i];
    tot = unique(b+1, b+n+1) - b - 1;
    MEX = 0, lft = k, diff = tot, cgb = n;
    // lft 剩下次数 diff 不同个数 cgb 可改动的数
    for(int i = 1; i <= tot && cgb; ++i) {
        while(b[i] != MEX && lft && cgb) ++MEX, --lft, --cgb, ++diff;
        if(b[i] == MEX && cgb) ++MEX, --cgb;
    }
    for(int i = 1; i <= n;) {
        int x = a[i], cnt = 0;
        while(x == a[i] && i <= n) ++cnt, ++i;
        if(cnt && x >= MEX) Q.push({x, cnt});
    }
    while(Q.size()) {
        auto [val, cnt] = Q.top(); Q.pop();
        if(lft + cnt <= k) --diff, lft += cnt;
    }
    while(Q.size()) Q.pop();
    printf("%d\n", diff - MEX);
}

int main() {
    int tt;
    scanf("%d", &tt);
    while(tt--) solve();
}