MEX vs DIFF

Created by LXC on Sat Jan 6 12:37:31 2024

https://codeforces.com/problemset/problem/1684/E

ranting: 2100

tag: binary search, brute force, constructive algorithms, data structures, greedy, two pointers

problem

给你一个大小为n的数组a，保证数组内元素非负，你可以执行以下操作k次：

在一次操作中将数组内任意一个数字改为任何一个非负整数。

现在定义这个数组的成本为DIFF(a)−MEX(a)，其中 DIFF(a) 为a数组内元素去重后的数量， MEX(a) 为数组中未出现的元素中最小的元素，
举个例子，MEX( { 1 , 2 , 3 } )=0 , MEX( { 0 , 1 , 2 , 4 , 5 } ) = 3。

现在给你数组a，求能实现的最小成本。

solution

成本是DIFF-MEX

我们将一个大于MEX的数放到MEX上，MEX将增大，DIFF可能减小

计算当前在k次操作后能达到的最大MEX，让后将大于MEX的数按照频次从小到大排序，优先选择频次较小的填充MEX前的空位。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n, k;
    cin >> n >> k;
    map<int,int> v;
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        v[x]++;
    }
    if (v.rbegin()->first+1-v.size()<=k) { //空位个数不超过k，操作完后DIFF=MEX
        cout << "0\n";
        return ;
    }
    // 找到填充k个空位后的mex
    int mex = 0;
    for (int j=0; j<k; mex++) {
        if (v.count(mex) == 0) j++;
    }
    while (v.count(mex)) mex++;
    // 大于mex的数可以拿来填充空位，我们优先出现频次小的数进行填充
    // 堆模拟 优先频次小
    priority_queue<int, vector<int>, greater<>> pq; // 小根堆
    for (auto& [i,j]:v) {
        if (i>mex) pq.emplace(j);
    }
    int ans = pq.size(); // DIFF-MEX，当前答案就是大于mex的不相同的数的个数。
    while (pq.size() && k) {
        auto x = pq.top();
        pq.pop();
        if (k-x>=0) k-=x, ans--;
        else k = 0;
    }
    cout << ans << "\n";
    
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}