[cf]Codeforces Round #792 (Div. 1 + Div. 2) E

E.MEX vs DIFF

前言 : 传送门 : 题意 : 给定一个非负数组 a [ ] a[] a[],和限定操作次数 k k k,询问经过最多 k k k 次操作,所能获得的最小 D I F F − M E X DIFF-MEX DIFF−MEX的值

操作定义 : 可以将 a [ i ] a[i] a[i]换成任意的非负整数 D I F F : DIFF: DIFF: 数组中不同数的个数 M E X : MEX: MEX: 数组中没有出现的最小的数

思路 : 考虑分析 D I F F − M E X DIFF-MEX DIFF−MEX，为了使这个值最小我们需要最大化 M E X MEX MEX

显然的,我们最大化 M E X MEX MEX能到的地方,就是我们能填 k k k个空隙的地方,如果不足 k k k个空隙,我们最大能填的必然是 n n n

因此我们可以先找出最大的 M E X MEX MEX

然后我们考虑进行填空隙

如果我们用前面出现多次的数来填的话, M E X MEX MEX不变但是 D I F F DIFF DIFF增加了

然后我们考虑使用 M E X MEX MEX后面的数来填,显然的如果我们按照出现次数从小到大,进行执行操作的话,我们可能会使得 D I F F DIFF DIFF减少

我们设 r e s = x . s i z e ( ) , ( x [ i ] > m e x ) res =x.size(),(x[i]>mex) res=x.size(),(x[i]>mex)

对于大于 M E X MEX MEX 并且能用来填充的数都会使得 D I F F − 1 DIFF-1 DIFF−1

所以我们只需要在大于 M E X MEX MEX的数中不断的令 R E S − 1 RES-1 RES−1即可

最后输出

code :

int a[N];
int n,k;
void solve(){
	mp.clear();
	
	cin>>n>>k;
	for(int i=1;i>a[i];
		mp[a[i]] ++ ;
	}
	
	int mx  = n;
	for(int i = 0,j = 0 ;i  MX)
	int len = v.size();
	
	for(auto x : v){
		if(k >= x){
			k-=x;
			len -- ;
		}
	}
	cout