题目链接:

Problem - 1630B - Codeforces

题意:

给定长度为n的序列,让你切分成k段,寻找最小的y-x使得切分后每一段在区间[x,y]内的数的数量都大于不在[x,y]内的数的数量,输出x,y及划分后k段每一段的下标。

思路:

考虑最差清况,k段内在[x,y]内的数比不在[x,y]内的数多一个,设序列中所有在[x,y]内的数由cnt_1个,不在[x,y]内的数有cnt_2个,则我们有

\left\{\begin{matrix} cnt_1\geq cnt2+k & & \\ cnt_1+cnt_2=n & & \end{matrix}\right. 。可第二个式子带入第一个式子得 cnt1\geqslant \left \lceil \frac{n+k}{2} \right \rceil  ,于是我们可以得到当cnt1满足这个条件时肯定是可以把序列切分成k段满足条件的,并且取等号的时候[x,y]得区间范围是最小的,我们令 cnt1= \left \lceil \frac{n+k}{2} \right \rceil 。

然后对原序列数组a拷贝一份(保存在b数组),对b数组从小到大排序,从1开始依次枚举b[cnt1]-b[1],b[cnt1+1]-b[2],...  (这样保证一定有cnt1个数是满足在区间[x,y]的,从而保证在[x,y]内的数的数量比不在区间[x,y]内的多k个),选择差最小的b[i]和b[cnt1+i-1]作为x和y。 

选出最小的y-x的x和y后,从头开始遍历a数组,设置一个计数变量cn=0,遇[x,y]内的数就cn++,遇不在[x,y]内的数就cn--,cn==1表示当前区间在[x,y]内的数比不在[x,y]内的数多一个,输出此时的左右端点,然后从右端点+1作为左端点继续找,直到找到k-1个这样的区间,最后一个输出[右端点+1,n]。

代码:

#include <bits/stdc++.h>

using namespace std;

const int inf=0x3f3f3f3f;
const int N=2e5+10; 
int t,n,k;
int a[N],b[N];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		int len=(n+k+1)/2;
		sort(b+1,b+n+1);
		int mi=inf,x,y,mx,my;
		for(int i=len;i<=n;i++){
			x=b[i-len+1],y=b[i];
			if(y-x<mi){
				mi=y-x;
				mx=x;
				my=y;
			}
		}
		printf("%d %d\n",mx,my);
		int cnt=0;
		int l=1,r=1;
		while(r<=n){
			if(k==1)
				break;
			if(a[r]>=mx&&a[r]<=my){
				cnt++;
			}
			else{
				cnt--;
			}
			if(cnt==1){
				cnt=0;
				printf("%d %d\n",l,r);
				k--;
				r++;
				l=r;
			}
			else
				r++;
		}
		printf("%d %d\n",l,n);
	}
}