给你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;
}