题目描述

洛谷 P10455 Genius Acm

Advanced CPU Manufacturer (ACM) 每天生产 n 台 CPU。质检部门会把若干台 CPU 分成一组进行测试：从这一组中取出 m 对 CPU（如果数量不足 2m 台，则尽量多取），每一对 CPU 的 RPD 为两台 CPU 性能值之差的绝对值。该组 CPU 的 SPD 为所有被取出配对的 RPD 平方和，只有当 SPD≤k 时，这一组 CPU 才能通过质检。

现在已知 n 台 CPU 的性能值 P1~Pn，需要把它们按原顺序划分成若干个连续段，使得每一段都能通过质检。求至少需要划分成多少段。

输入

每个测试点包含多组数据，第一行一个整数T给出数据组数。
对于每组数据，第一行三个整数n, m, k，第二行n个整数P1~Pn。

输出

对于每组数据，输出一个整数表示答案。

样例输入

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9

样例输出

2
1

提示

思路

首先考虑SPD的计算方式,因为是随机抽取,因此即使是最坏的情况也能通过
那么最坏的情况是什么? 即最大-最小,次大-次小,… 此时SPD在序列不变时,取最大值
所以只需要每次计算出SPD符合条件的最大截取范围即可

首先,每次枚举终点肯定会超时
可以采用倍增的方式，用logn的时间得到最大的划分区间，同时用快速排序以n log n 的复杂度判断，同时有的区间相互包含，因此可以少排一段序，最终归并即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n,m,p[500005],t[500005],la[500005],tmp[500005],last,ans;
ll k;
void ms(int l,int r,int mid){
    int i=l,j=mid+1,k=l;
    while (i<=mid && j<=r){
        if (t[i]<=t[j]){
            tmp[k]=t[i];
            k++;
            i++;
        }else{
            tmp[k]=t[j];
            k++;
            j++;
        }
    }
    while (i<=mid){
        tmp[k]=t[i];
        k++;
        i++;
    }
    while (j<=r){
        tmp[k]=t[j];
        k++;
        j++;
    }
    for (int i=l;i<=r;++i){
        t[i]=tmp[i];
    }
}
 
void sor(int st,int ed){
    for (int i=1;i<=last;++i) t[i]=la[i];
    sort(t+last+1,t+ed+1);
    ms(st,ed,last);
}
 
ll ch(int st,int ed){
    ll ret=0;
    for (int i=st;i<=ed;++i) t[i-st+1]=p[i];
    ed=ed-st+1;st=1;
    sor(1,ed);
    int mid=(st+ed)>>1;
    for (int i=1;i<=min(mid,m);++i) ret+=(ll)(t[i]-t[ed-i+1])*(t[i]-t[ed-i+1]);
    if (ret<=k && ed<=n){
        for (int i=1;i<=ed;++i) la[i]=t[i];
        last=ed;
    }
    return ret;
}
 
void solve(){
    scanf("%d %d %lld",&n,&m,&k);
    for (int i=1;i<=n;++i) scanf("%d",&p[i]);
    int l=1;
    ans=0;
    while (l<=n){
        int len=1,r=l;
        last=0;
        while (len){
            if (r+len<=n && ch(l,r+len)<=k) {
                r+=len;
                len<<=1;
            }else{
                len>>=1;
            }
        }
        ans++;
        l=r+1;
    }
    printf("%d\n",ans);
}
 
int main(){
    // freopen("geniusacm.in", "r", stdin);
    // freopen("geniusacm.out", "w", stdout);
    int t;
    cin>>t;
    while (t--) solve();
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/65/