Codeforces Round #768 (Div. 2) D

题意：

给定一个长度为 $N$ 的数组，和一个数 $k$ 。你需要选择一个区间 $[x,y]$ ，使得可以将数组分为 $k$ 个子数组，每个子数组中落在区间 $[x,y]$ 的数严格大于不落在区间中的数。

最小化 $y-x$ 的值，并输出分割方案。

思路：

要想找到最短一个区间，然后使的这个序列分成k段，每一段在区间里的数的数量要严格大于区间外的数的数量，我们可以枚举左端点然后二分右端点。那么如何一个区间合不合适呢？

例如，我们当前取的区间是 $[l, r]$ ,我们要统计在这个区间的数的数量和区间外的数的数量。

观察数据范围，我们很容易可以想到，我们可以采用桶计数的方法，对桶取一个前缀和。就可以解决上面的问题。

同时题目要求分成k段，每一段在区间里的数的数量要严格大于区间外的数的数量所，所以 $s u m (l, r) > = n - s u m (l, r) + k$ ,

所以check函数：

bool chk(int l,int r){
	return 2*(sum[r]-sum[l-1])-n>=k;
}

二分就不写了。

继续分析，我们发现如果要让区间尽量小，即R-L尽量的小，当右端点不断往右时，只有左端点不断也右，长度才会更小。所以我们可以考虑采用双指针的方式来求，最小的 y-x的值。

求出 $[x, y]$ 我们要考虑如何输出。我们可以从头遍历，如果满足区间里的数的数量要严格大于区间外的数的数量，就把它输出，输出前k-1段，那么剩余最后一段最长的肯定也满足条件，因为就是从这个性质求得的 x，y；

双指针代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N],sum[N],t[N],n,m,k;
bool chk(int l,int r){
	return 2*(sum[r]-sum[l-1])-n>=k;
}
void solve(){
	cin>>n>>k;
	t[0]=0;
	rep(i,1,n){
		sum[i]=0;
		t[i]=0;
	}
	rep(i,1,n){
		cin>>a[i];
		t[a[i]]++;
	}
	rep(i,1,n){
		sum[i]=sum[i-1]+t[i];
	}
	int x=0,y=1e18;
	for(int L=1,R=1;R<=n;R++){
		while(chk(L,R)&&L<=R){
			if((R-L)<(y-x)){
				x=L;y=R;
			}
			++L;
		}
	}
	cout<<x<<" "<<y<<endl;
	int in=0,out=0,ctk=1,pre=1,now;
	rep(i,1,n){
		if(ctk>=k) break;
		if(a[i]>=x&&a[i]<=y) in++;
		else out++;
		if(in>out){
			cout<<pre<<" "<<i<<endl;
			pre=i+1;
			in=0;
			out=0;
			ctk++;
		}
	}
	cout << pre << " " << n << endl;
}
signed main(){
	int _;cin>>_;
	while(_--) solve();
	return 0;
}