109. 天才ACM（二分、倍增

题源
倍增比二分快了一个logn

#pragmaGCCoptimize(3)#include<bits/stdc++.h>#include<iostream>usingnamespacestd;#defineintlonglongintK,M,N,T;constintMAX_LEN=5e5+9;intarr[MAX_LEN];intbrr[MAX_LEN]={};template<typenameT>inlineTread(){T X=0;registerboolflag=1;registercharch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')flag=0;ch=getchar();}while(ch>='0'&&ch<='9'){X=(X<<1)+(X<<3)+ch-'0';ch=getchar();}if(flag)returnX;return~(X-1);}inlineboolcheck(intst,intmid){intpowSum=0;memcpy(brr+1,arr+st,mid*sizeof(int));// for (int i = st;i<=6;i++)cout<<arr[i]<<"\n";// for (int i = st;i<=6;i++)cout<<brr[i]<<"\n";sort(brr+1,brr+mid+1);for(inti=1;i<=M;i++){if(i<mid-i+1){powSum+=pow(brr[mid-i+1]-brr[i],2);// cout<<powSum<<"ps\n";}elsebreak;}// cout<<st<<" "<<mid<<" "<<powSum<<"--\n";if(powSum<=T)returntrue;returnfalse;}signedmain(){K=read<int>();while(K--){// scanf("%lld %lld %lld",&N,&M,&T);N=read<int>();M=read<int>();T=read<int>();for(inti=1;i<=N;i++){// scanf("%lld",&arr[i]);arr[i]=read<int>();}intdst=1,ans=0,end=1;intmulti=1;while(dst<=N){//段的起点小于等于nmulti=1;while(multi!=0){//无法倍增为止if(end+multi<=N&&check(dst,end+multi-dst+1)){//如果倍增结束点+multi<=n,并且检查起点到倍增后的结束点满足//则结束点更新，倍增增加end+=multi;multi<<=1;}else{multi>>=1;//否则减少}}ans++;dst=end+1;//更新起点为倍增后的下一个}printf("%lld\n",ans);}return0;}```