Acwing 109. Genius ACM （倍增 + 歸并排序）

題意

給出n個數Ai，問最少将這n個數分成幾段，使每一段的校驗值小于k。

一段數的校驗值定義為：

從集合 S 中取出 M對數(即 2∗M 個數，不能重複使用集合中的數，如果 S 中的整數不夠 M 對，則取到不能取為止)，使得“每對數的差的平方”之和最大，這個最大值就稱為集合 S 的“校驗值”。

1 < = N , M < = 500000 , 0 < = K < = 1 e 18 , 0 < = A i < = 2 20 1<= N , M <=500000,0<=K<=1e18,0<=A_i<=2^{20} 1<=N,M<=500000,0<=K<=1e18,0<=Ai​<=220

思路

貪心很容易得到校驗值，就是選最大和最小的差的平方+次大和次小的差平方+……+。

要想分段數最小，每一段就要盡可能多的數。對于一個左端點，使右端點盡可能大。

一種很樸素的思路是一點一點擴充右端點，每次擴充排序算校驗值，但是這樣擴充太慢，并且涉及大量的快排，顯然會逾時。

優化：

擴充可以考慮使用倍增思想，以二進制的方式擴充。

每次擴充其實隻有擴充的部分需要重新排序，可以考慮隻對擴充的部分使用快排，再使用歸并排序合并。

代碼

#include <bits/stdc++.h>
using namespace std;
#define doub(x) (x)*(x)
typedef long long LL;
const int maxn=5e5+5;
int t,n,m,ans;
LL k;
int p[maxn],a[maxn];
LL b[maxn];

inline void merge(int l,int mid,int r){
    int i=l,j=mid,k=l;
    while (i<mid && j<=r){
        if(a[i]<a[j])b[k++]=a[i++];
        else b[k++]=a[j++];
    }

    while (i<mid)b[k++]=a[i++];
    while (j<=r)b[k++]=a[j++];
}

inline bool check(int l,int mid,int r){
    for(int i=mid;i<=r;++i)a[i]=p[i];

    sort(a+mid,a+r+1);

    merge(l,mid,r);

    LL sum=0;
    for(int i=0;i<m && r-i>l+i ;++i)
        sum+=doub(b[r-i]-b[l+i]);

    if(sum>k)return false;

    for(int i=l;i<=r;++i)a[i]=b[i];
    return true;
}

inline void sol(){
    ans=0;
    int l=0,r=0,len=1;
    a[l]=p[l];
    while (r<n){
        if(!len){
            ++ans;
            l=(++r);
            a[l]=p[l];
            len=1;
        }
        else if(r+len<n && check(l,r+1,r+len)){
            r+=len;
            if(r==n-1)break;
            len<<=1;//倍增思想，成倍增長
        }
        else len>>=1;//倍增思想，無法成倍增長時，嘗試縮小一倍增長
    }
    if(r==n-1)++ans;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;
    while (t--){
        cin>>n>>m>>k;
        for(int i=0;i<n;++i)cin>>p[i];

        sol();
        cout<<ans<<endl;
    }
    return 0;
}
           

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-XXXuGWwa-1618490379999)(https://yhsm-images.oss-cn-hangzhou.aliyuncs.com/imgs/image-20210409145313572.png)]