Genius ACM（归并+倍增）

题目描述

给定一个整数 MM，对于任意一个整数集合 SS，定义“校验值”如下:

从集合 SS 中取出 MM 对数(即 2∗M2∗M 个数，不能重复使用集合中的数，如果 SS 中的整数不够 MM 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 SS 的“校验值”。

现在给定一个长度为 NN 的数列 AA 以及一个整数 TT。

我们要把 AA 分成若干段，使得每一段的“校验值”都不超过 TT。

求最少需要分成几段。

输入格式

第一行输入整数 KK，代表有 KK 组测试数据。

对于每组测试数据，第一行包含三个整数 N,M,TN,M,T 。

第二行包含 NN 个整数，表示数列A1,A2…ANA1,A2…AN。

输出格式
对于每组测试数据，输出其答案，每个答案占一行。

数据范围

1≤K≤12
1≤N,M≤500000
0≤T≤10^18
0≤Ai≤220

样例

输入样例：
2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9
输出样例：
2
1

如果要使划分的区间数量尽可能的小，就要使每一段的数尽可能的大，首先探险选取区间的最大值和最小值，这道题如果二分的话，左右区间增加很慢，会超时。所以只能使用倍增，把步数一步一步地扩大，如果当前步数不满足，再把步数缩小一半，寻找最小值。

这道题给的时间限制是10秒，用倍增4063ms就可以，二分应该会超时。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include <queue>
#include <vector>
#include<map>
const int INF = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double ld;
int i,j;
int cnt;
using namespace std;
ll n,m,k,p[500005],t[500005],la[500005],tmp[500005],last,ans;
void ms(ll l,ll r,ll mid)
{
    ll 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 (ll i=l; i<=r; ++i)
    {
        t[i]=tmp[i];
    }
}

void sor(ll st,ll ed)
{
    for (ll i=1; i<=last; ++i)
        t[i]=la[i];
    sort(t+last+1,t+ed+1);
    ms(st,ed,last);
}

ll ch(ll st,ll ed)
{
    ll ret=0;
    for (i=st; i<=ed; ++i) t[i-st+1]=p[i];
    ed=ed-st+1;
    st=1;
    sor(1,ed);
    ll mid=(st+ed)>>1;
    for(i=1; i<=min(mid,m); ++i)
        ret+=(t[i]-t[ed-i+1])*(t[i]-t[ed-i+1]);
    if(ret<=k && ed<=n)
    {
        for(i=1;i<=ed;++i)
        la[i]=t[i];
        last=ed;
    }
    return ret;
}

void solve()
{
    scanf("%lld %lld %lld",&n,&m,&k);
    for(i=1; i<=n; ++i)
        scanf("%lld",&p[i]);
    ll l=1;
    ans=0;
    while(l<=n)
    {
        ll 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("%lld\n",ans);
}

int main()
{
    ll t;
    cin>>t;
    while (t--)
        solve();
    return 0;
}