E. MEX vs DIFF
题意:给定一个数组a[], n个元素,最多能操纵k次,把任何数字变成一个非负整数,使得diff(a) - mex(a)最小, diff(a):为数组中不同元素的个数。
思路:
考虑使得diff(a) - mex(a)减少, 若mex(a) = x,那么[0, x - 1]必出现。 所以可以转化为 >= mex 的不同元素的个数。
可以贪心使得mex尽可能变大,然后在此条件下,尽量用 >= mex的数去填补空缺,同样为了使得ans最优,那么就要优先使用出现次数最小的>=mex的数,因为此值都可拿去填补空缺,那么diff + t - 1, mex + t 最优解会减少1 ,否则diff + t, mex + t, 最优解保持不变。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eb push_back()
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
ll a[maxn];
map <ll, int> mp;
int main() //O(n) O(nlogn)
{
int T;
scanf("%d", &T);
while(T --)
{
int n, k;
scanf("%d %d", &n, &k);
int temp = k;
mp.clear();
for(int i = 1 ; i <= n ; i ++)
{
scanf("%lld", &a[i]);
mp[a[i]] ++;
}
int mex = 0;
for(int i = 0 ; i <= n ; i ++)
{
if(mp.count(i))
mex ++; // mex = 1
else
{
if(k == 0)
break;
if(k > 0)
k --, mex ++; // mex = 2
}
}
vector <int> alls;
for(auto t : mp)
{
if(t.first > mex - 1)
alls.push_back(t.second);
}
sort(alls.begin(), alls.end());
int cnt = 0;
for(int i = 0 ; i < alls.size() ; i ++)
{
if(temp >= alls[i])
{
temp -= alls[i];
cnt ++;
}
else break;
}
printf("%d\n", int(alls.size()) - cnt);
}
return 0;
}