Codeforces #792 : E. MEX vs DIFF

ダメダメだった回。
https://codeforces.com/contest/1684/problem/E

問題

N要素の整数列Aのコストを、(ユニークな要素数)-(MEX値)とする。
AのうちK要素を任意の非負整数にできるとき、コスト値を最小化せよ。

解法

MEX値が大きいほどコストが下がるので、MEX値を総当たりしていこう。
もしある値vがA中に現れない場合、MEX値をv+1以上にするには、どこかの値をvにしなければならない。
その場合、ユニークな要素数を減らしたいので、v以上の値のうち頻度の小さいものから優先的に持ってくるようにしよう。

int T,N,K;
int A[101010];
set<int> S[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		map<int,int> M;
		FOR(i,N) {
			S[i+1].clear();
			cin>>x;
			M[x]++;
		}
		
		if(K>=N) {
			cout<<0<<endl;
			continue;
		}
		
		set<pair<int,int>> A,B;
		FORR2(a,b,M) B.insert({b,a});
		
		int ret=N;
		
		int sum=0;
		int can=0;
		FOR(i,N+2) if(can<=K) {
			if(M[i]==0) {
				while(sum>can) {
					auto p=*A.rbegin();
					A.erase(p);
					B.insert(p);
					sum-=p.first;
				}
				while(B.size()&&sum+B.begin()->first<=can) {
					auto p=*B.begin();
					A.insert(p);
					B.erase(p);
					sum+=p.first;
				}
				ret=min(ret,(int)B.size());
				
				can++;
			}
			else {
				
				if(A.count({M[i],i})) {
					A.erase({M[i],i});
					sum-=M[i];
					while(B.size()&&sum+B.begin()->first<=can) {
						auto p=*B.begin();
						A.insert(p);
						B.erase(p);
						sum+=p.first;
					}
				}
				else {
					B.erase({M[i],i});
				}
			}
		}
		
		cout<<ret<<endl;
	}
}

まとめ

これはそこまで苦労してないな。