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;
}