CH109 Genius ACM 题解报告

mac2022-06-30  95

题目传送门

【题目大意】

【思路分析】

首先显然可知,当一段区间内选出的$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

最新回复(0)