《算法竞赛进阶指南》 天才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≤121≤K≤12,
1≤N,M≤5000001≤N,M≤500000,
0≤T≤10180≤T≤1018,
0≤Ai≤2200≤Ai≤220

输入样例：

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

输出样例：

2
1

解题思路：

/*
大概思路：
使用倍增的方法先求出区间[L, L + len]的校验值
若成立则令L += len , len <<= 1
若不成立则令len >>= 1直到len为0循环结束

每对数的差的平方”之和最大因此要使它最大则应该是
最小的数与最大的数配对，次小的数与次大的数配对
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

LL T;
int n, m;
int a[N], temp[N], t[N];
//a[N]为A数组,temp为归并排序中的临时数组, t[N]为当前正在倍增的数组
LL sq(int x)
{
    return (LL)x * x;
}

bool check(int l, int mid, int r)
{
    for (int i = mid; i < r; i ++ ) t[i] = a[i];//因为[l, mid)在上一轮以及被排序计算过，所以直接从mid开始

    sort(t + mid, t + r);//将t的区间排序

    int i = l, j = mid, k = 0;
    while (i < mid && j < r)//将排好序的t放入temp中，此时temp里面的数都是从小到大排序的
    {
        if (t[i] < t[j]) temp[k ++ ] = t[i ++ ];
        else temp[k ++ ] = t[j ++ ];
    }

    while (i < mid) temp[k ++ ] = t[i ++ ];
    while (j < r) temp[k ++ ] = t[j ++ ];

    LL sum = 0;
    for (int i = 0; i < m && i < k; i ++, k -- )//检查校验值是否符合要求，题目说了校验值是
        sum += sq(temp[i] - temp[k - 1]);       //每对数的差的平方”之和最大因此要使它最大则应该是
                                                //最小的数与最大的数配对，次小的数与次大的数配对
    return sum <= T;                            //因为temp从小到大排序因此选择第一个与最后一个配对
}

int main()
{
    int cnt;
    cin >> cnt;
    while (cnt -- )
    {
        scanf("%d %d %lld", &n, &m, &T);
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

        int ans = 0, len;
        int start = 0, last = 0;
        while (last < n)
        {
            len = 1;
            while (len)
            {
                if (last + len <= n && check(start, last, last + len))//判断[start, last + len)是否符合要求
                {
                    last += len, len <<= 1;//若成立利用倍增思想扩大范围

                    if (last >= n) break;//若last >= n，则last + len比大于n + 1题解结束

                    for (int i = start; i < last; i ++ )//经过check后数组temp中的[start, len]以及被排序过
                        t[i] = temp[i - start];//将他放入倍增数组t以免重复排序
                }
                else len >>= 1;//若不成立缩小范围
            }

            start = last;//当len == 0说明该区间[start, last]已选得最大区间长度的符合要求的校验值
            ans ++ ;//所以开始下一个区间的选取
        }

        printf("%d\n", ans);
    }
}