题解

D. Range and Partition 1800 思维

https://codeforces.com/contest/1631/problem/D
题解：由于严格大于，故其最终前缀和s[n]>=k,而当s[n]>=k，s[0]=0,每步至多下降1，故其中必有至少k个点满足s[i]=x（1<=x<=k),故符合题意，故只需双指针找出最小的满足题意的区间即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=1e18;
int a[N],s[N];

void solve(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++) s[i]=0;
	for(int i=1;i<=n;i++) cin>>a[i],s[a[i]]++;
	for(int i=1;i<=n;i++) s[i]=s[i-1]+s[i];
	int r=1;
	int ans=1e18,w=(n+k+1)/2,L=1,R=n;
	for(int l=1;l<=n;l++){
		while(r<n&&s[r]-s[l-1]<w) r++;
		if(s[r]-s[l-1]>=w){
			if(ans>r-l) L=l,R=r;
			ans=min(ans,r-l);
		}
	}
	cout<<L<<" "<<R<<endl;
	int sum=0,cnt=1,pre=1,now=1;
	for(int i=1;i<=n;i++){
		if(cnt==k){
			cout<<pre<<" "<<n<<endl;break;
		}
		if(a[i]>=L&&a[i]<=R) a[i]=1;
		else a[i]=-1;
		sum+=a[i];
		if(sum==cnt){
			cout<<pre<<" "<<i<<endl;
			pre=i+1;
			cnt++;
		}
	}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
}

E. MEX vs DIFF 2100

https://codeforces.com/problemset/problem/1684/E
题解：有两个变量，我们尝试枚举（固定）mex（显然O(n))，最小化miff来达到目的。
对于给定的mex,我们发现将出现次数较小的>mex的数移入<mex中最优，再通过map维护出现次数，即可O(nlogn+nsqrt(k））.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int our[N];
map<int,int> num,f;
void solve(){
	num.clear();f.clear();
	int n,k;cin>>n>>k;
	for(int i=0;i<=n;i++) our[i]=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(x<=n)
		our[x]=1;
		num[x]++;
	}
	for(int i=1;i<=n;i++)
	our[i]=our[i-1]+our[i];
	for(auto [_,it]:num){
		f[it]++;
	}
	int DIFF=0,MEX;
	DIFF=num.size();
	int need=0,ans=DIFF;
	for(int i=1;i<=n+1;i++){
		if(num[i-1]) DIFF-=1;
		if(num[i-1]) f[num[i-1]]--;  
		MEX=i;
		int diff=DIFF;
		if(our[i-1]+k<i) continue;
		need=k;
		for(auto [x,y]:f){
			if(need>=x*y){
				need-=x*y;diff-=y;
			}
			else{
				diff-=need/x;break;
			}
		}
		ans=min(ans,diff);
	}
	cout<<ans<<endl;
}
signed main(){
	int T;
	cin>>T;
	while(T--) 
	solve();
}