题目描述

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

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

现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$。

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

求最少需要分成几段。

输入格式
第一行输入整数 $K$，代表有 $K$ 组测试数据。

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

第二行包含 $N$ 个整数，表示数列$A_1,A_2…A_N$。

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

数据范围
$1≤K≤12$
$1≤N,M≤500000$
$0≤T≤10^{18}$
$0≤A_i≤2^{20}$

样例

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

归并思想+倍增

个人认为,这道题目难点不在倍增,而是归并合并,可能是因为我太菜了.

思路大致如下:首先我们要区间取数尽量地大,那么我们很容易地想到,贪心+排序,相信这个是很好思考到的,每一次贪心选取,当前待选择区间,中的最大数和最小数.

因此我们可以枚举左端点和右端点,显然二分是一个不错的方法,但是有一个问题.

我们发现,这道题目如果说用二分做的话,假如题目中右区间增加缓慢的话,那么毫无疑问这道题目会超出时间范围,那么这道题目,我们只能够使用倍增,这个非常优秀的二分逆运算.

这道题目之所以要用到归并思想,是因为如果所有排序的话,那么和二分问题一样,我们同样容易超时,但是归并没有这个问题,因为归并本身就是合并两个有序区间.而我们之前问题的待选择区间,是已经有序的.

倍增的算法,可以参考lyd老师的思路因为我说的不太好,如果不在意可以看后面的瞎扯,也就是常规的倍增思路,不断地扩大当前的步伐,如果发现当前这一步步伐太大,不满足题意的话,那么我们就将这一步步伐取一半,接着算.

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define sqr(a) (a)*(a)
const int N=5e5+10;
int n,m,p[N],ans,l,r;
ll b[N],a[N],k;
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++];
}
bool check(int l,int mid,int r)
{
    fir(i,mid,r)
        a[i]=p[i];
    sort(a+mid,a+r+1);
    merge(l,mid,r);
    ll sum=0;
    for (int i=1; i<=r-l+1>>1 && i<=m; i++)
        sum+=sqr(b[r-i+1]-b[l+i-1]);
    if (sum<=k)
    {
        for (int i=l; i<=r; i++)
            a[i]=b[i];
        return true;
    }
    else
        return false;
}
void init()
{
    l=r=0;
    ans=0;
    cin>>n>>m>>k;
    fir(i,1,n)
        cin>>p[i];
}
void work()
{
    int len=1;
    l=r=1;
    a[l]=p[l];
    while (r<=n)
        if (!len)
        {
            len=1;
            ans++;
            l=(++r);
            a[l]=p[l];
        }
        else if (r+len<=n && check(l,r+1,r+len))
        {
            r+=len;
            len<<=1;
            if (r==n)
                break;
        }
        else
            len>>=1;
    if (r==n)
        ans++;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while (t--)
    {
        init();
        work();
        cout<<ans<<endl;
    }
    return 0;
}