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

推荐阅读

商业承兑汇票是什么意思商业承兑汇票的理解

在“再见阿郎”中的刘金虎怎么又是金鹏？

一斤几克重，一斤等于多少千克

忙碌了多少天辛苦了多少年是啥歌快去听一下吧

煤炭公司起名大全免费煤炭行业起名大全

天麻能泡白酒吗天麻可以和虫草花一起煲汤吗

关于洛阳昊远机械设备有限公司简述洛阳昊远机械设备有限公司

梦见水里有黑鱼在游

我们好像在哪见过歌词我们好像在哪见过歌词歌谱

五岳奇险天下第一山是哪座山天下第一山是哪座山

etc不抬杆可以倒回吗 etc不抬杆可以倒回会被扣分吗

节日由来英语节日由来

教你如何使用迅雷离线下载[新发布]

如何通过女人面相看婚姻哪些面相的女人婚姻好

孕妇梦见和别人吵架孕妇梦见别人挣了很多钱

皮蛋是生的还是熟的怎么判断皮蛋是生的还是熟的

喝番茄汁有什么好处番茄汁的好处有哪些

梦见和当官的同学在一起商人梦见当官的同学

瑜伽入门动作图解瑜伽入门动作图解上

“八岐之术”是什么？