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<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】

Codeforces 1684 E. MEX vs DIFF

推荐阅读

越在乎你才会越嫌弃你的星座，天蝎上榜！

白羊座最适合的运动

《四季豆一定要焯水吗》

关于来不及诉说简述来不及诉说

肉煎饺的做法步骤肉煎饺的做法步骤

荞麦茶的功效有哪些荞麦茶有什么作用功效

保护视力的绘画作品保护视力的绘画作品画法

大连金普新区文旅场馆7月19日起取消查验核酸报告

芋头和香芋一样吗？芋头什么人不能多吃

江苏省公务员abc类区别江苏省公务员abc类的区别

王丽云主演的电视剧有哪些王丽云演的全部电视剧

鱼鳞痣怎么祛除掉鱼鳞痣怎么祛除

发朋友圈运动的幽默句子发朋友圈运动句子

形容教室里很多人的成语

职工医保和城乡居民医保哪个划算？交哪个好

电脑版微信怎么发朋友圈电脑版微信怎么发朋友圈视频

攀升MaxBook P2参数_攀升MaxBook P2配置

伊美婷成分伊美婷胶原蛋白安全吗

属兔的适合住什么楼层最好住几楼大吉？

铝锅煮汤对人体有害吗，不建议经常使用铝锅煮汤