题意给你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】
推荐阅读
- Rated for Div. 2 Educational Codeforces Round 138 A-E
- [题解] Codeforces Dytechlab Cup 2022 1737 A B C D E 题解
- Div. 2 Codeforces Round #822 A-F
- Div. 2 Codeforces Round #823 A-D
- [题解] Codeforces Global Round 22 1738 A B C D E F 题解
- realmex有nfc功能吗
- realmex使用技巧
- reamex怎么读
- 怎么使用amex
- realme x2怎么备份文件