hihoCoder#1384 : Genius ACM(贪心+倍增+归并排序思想)

题意：添加链接描述

题解：对于一个集合，肯定是应该选取最大的 M M M个数和最小的 M M M个数，最大和最小构成一对，次大和次小 ⋯ \cdots ⋯，为了使得每一段的”校验值“都不得超过T。求最少需要分成几个端。所以从头开始，那么就应该让每一段尽量长，贪心选取到达结尾是的段数就是答案。首先每一段的最后如何选取，通过二分选取，对每一段进行排序，复杂度最后是 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)，但是使用倍增来处理，倍增过程如下：

1. 初始化p=1，R=L。
2. 求出 [ L , R + p ] [L,R+p] [L,R+p]这一段区间的校验值，若校验值 ≤ T \le T ≤T，则 R + = p ， p ∗ = 2 R+=p，p*=2 R+=p，p∗=2，否则 p / = 2 p/=2 p/=2
3. 重复上一步，直到 p p p的值变为 0 0 0，此时 R R R即为所求。

这个循环最多重复 O ( l o g N ) O(logN) O(logN)次，每次循环对 O ( R − L ) O(R-L) O(R−L)的一段进行排序，完成求解累计拓展长度为 N N N，所以总体复杂度为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。最后发现如果只对新增的长度部分排序，然后合并新界两段，使得整体复杂度降为 O ( N l o g N ) O(NlogN) O(NlogN)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+50;
int T,n,m;
ll t,a[N],tmp[N],b[N];
void merge(int l,int mid,int r)
{
    int i=l,j=mid;
    for(int k=l;k<=r;k++){
        if(j>r||i<mid&&tmp[i]<tmp[j])b[k]=tmp[i++];
        else b[k]=tmp[j++];
    }
}
bool check(int l,int mid,int r)
{
    for(int i=mid;i<=r;i++)tmp[i]=a[i];
    sort(tmp+mid,tmp+r+1);
    merge(l,mid,r);
    ll sum=0;
    for(int i=1;i<=(r-l+1)>>1&&i<=m;i++)sum+=(b[r-i+1]-b[l+i-1])*(b[r-i+1]-b[l+i-1]);
    if(sum<=t){
        for(int i=l;i<=r;i++)tmp[i]=b[i];
        return true;
    }
    return false;
}
int work()
{
    int l=1,r=1,ans=0,len=1;
    tmp[l]=a[l];
    while(r<=n){
        if(!len){
            ans++;
            l=(++r);
            tmp[l]=a[l];
            len=1;
        }else if(r+len<=n&&check(l,r+1,r+len)){
            r+=len;
            if(r==n){
                ans++;
                break;
            }
            len<<=1;
        }else len>>=1;
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%lld",&n,&m,&t);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        printf("%d\n",work());
    }
    return 0;
}