题目传送门
【题目大意】
【思路分析】
首先显然可知，当一段区间内选出的$M$对数分别是，最大和最小一对，次大和次小一对，……，第$M$大和第$M$小一对，此时的“校验值”最大，如果这段区间的最大“校验值”满足条件了，那么这个区间就是合法的。我们考虑将数列$A$从头开始分段，在满足每段区间合法的情况下让区间尽量包含更多的数，到达结尾时整个数组分成的段数就是答案。
于是我们要解决的问题就是，当确定一个区间的左端点$L$后，右端点$R$在满足$A[L]～A[R]$的“校验值”不超过$T$的情况下，最大能取到多少。
求长度为$N$的一段区间的“校验值”需要排序配对，时间复杂度为$O(N*log_2N)$。当“校验值”上限$T$比较小时，如果在整个$L～N$的区间上二分右端点$R$，二分的第一步就要检验$(N-L)/2$这么长的一段，最终右端点$R$却可能只扩展了一点，浪费了很多时间，于是我们考虑使用倍增算法。
倍增过程如下：
1.初始化：$p=1,R=L$
2.求出$[L,R+p]$这一段区间的“校验值”，若$\le T$，则$R+=p,p*=2$，否则$p/=2$
3.重复上一步，直到$p$的值变为0，此时$R$即为所求
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define rg register 5 #define ll long long 6 #define go(i,a,b) for(rg int i=a;i<=b;i++) 7 using namespace std; 8 const int N=500002; 9 int K,n,m,a[N],b[N],c[N]; 10 ll t; 11 bool check(int l,int mid,int r){ 12 go(i,mid,r) b[i]=a[i]; 13 sort(b+mid,b+r+1); 14 int i=l,j=mid; 15 go(k,l,r) 16 if((i<=mid-1&&b[i]<b[j])||j>r) c[k]=b[i++]; 17 else c[k]=b[j++]; 18 i=l,j=r;int num=min(m,(r-l+1)/2);ll sum=0; 19 while(num--) 20 sum+=(ll)(c[i]-c[j])*(c[i]-c[j]),i++,j--; 21 if(sum<=t){ 22 go(i,l,r) b[i]=c[i]; 23 return 1; 24 } 25 return 0; 26 } 27 int main(){ 28 scanf("%d",&K); 29 while(K--){ 30 scanf("%d%d%lld",&n,&m,&t); 31 go(i,1,n) scanf("%d",&a[i]); 32 int l=1,r=1,p=1,ans=0;b[1]=a[1]; 33 while(l<=n){ 34 if(r+p<=n&&check(l,r+1,r+p)) r+=p,p*=2; 35 else p/=2; 36 if(!p||r==n) ans++,l=++r,p=1,b[l]=a[l]; 37 } 38 printf("%d\n",ans); 39 } 40 return 0; 41 } 代码实现转载于:https://www.cnblogs.com/THWZF/p/11276206.html
