思路

这道题耗了我一个上午。今天上午因为得知 NOIp 2018 成绩之后无法稳定心态去上课，所以翘课来机房写题。而当我看了半天的书和题解之后，我整合出了一个思路。

我们首先把整个序列存入\(pre[]\)数组之中，然后我们从端点\(L=1\)开始枚举右端点。我们选择倍增来加速。写一个\(check(num)\)函数来检测该区间内的校验值是否符合标准。校验值的计算策略是进行排序之后取最大和最小、次大和次小、…进行计算。我们排序可以使用归并排序的思想，因为我们的区间长度是以\(2\)为底的幂，且是从小到的枚举的，所以我们每次只需要排序区间右半部分，然后进行合并操作即可。具体看代码吧。

代码

// CH0601.cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
const int maxn = 5000020;
using namespace std;
int pre[maxn], seq[maxn], tmp[maxn], n, m, k;
long long T;
long long doubleTimes(long long x)
{
    return x * x;
}
bool checkHash(int l, int r, int nr)
{
    if (l == r)
        seq[l] = pre[l];
    copy(pre + r + 1, pre + nr + 1, seq + r + 1);
    long long sum = 0;
    sort(seq + r + 1, seq + nr + 1);
    merge(seq + l, seq + r + 1, seq + r + 1, seq + nr + 1, tmp + l);
    int p1 = l, p2 = nr, pr = 0;
    while (p1 < p2 && pr < m && sum <= T)
        sum += doubleTimes(tmp[p1++] - tmp[p2--]), pr++;
    if (sum <= T)
        copy(tmp + l, tmp + nr + 1, seq + l);
    return (sum <= T);
}
int main()
{
    scanf("%d", &k);
    while (k--)
    {
        scanf("%d%d%lld", &n, &m, &T);
        for (int i = 1; i <= n; i++)
            scanf("%d", &pre[i]);
        int segs = 0;
        int p = 1, R;
        for (int L = 1; L <= n; L = R + 1)
        {
            p = 1, R = L;
            for (int i = 1; i <= n; i++)
                seq[i] = pre[i];
            while (p != 0 && R <= n)
                if (checkHash(L, R, min(n, R + p)))
                    R += p, p <<= 1;
                else
                    p >>= 1;
            segs++;
        }
        printf("%d\n", segs);
    }
    return 0;
}