形式化题目

给定整数 $M$、长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$ 以及非负整数阈值 $T$。

对任意整数集合 $S$，定义其校验值 $V(S)$：从 $S$ 中取出 $k = \min\big(M, \lfloor |S| / 2 \rfloor\big)$ 对互不相同的数（每对两个数不能重复使用，$S$ 中的数不够 $M$ 对时取到不能取为止），使得"每对数的差的平方"之和最大，这个最大值就是校验值：

目标：把 $A$ 切成最少的若干连续段，使每一段的校验值都不超过 $T$，输出段数。

样例 $A = (8, 2, 1, 7, 9)$、$M = 1$ 时，从第一个位置起各候选前缀的校验值如下（$M=1$ 即每段只取差的平方最大的一对）：

$T = 49$ 时最长可行前缀只到第 4 个数，剩下 $(9)$ 单独成段，答案 2；$T = 64$ 时全段校验值 $(9-1)^2 = 64 \leqslant 64$，答案 1，与样例输出一致。这张表还藏着两个关键信息：配对总发生在排序后的两端，且前缀越长校验值不减——前者给出校验值的快速算法，后者是二分合法性的来源。

正解

思路

朴素做法与瓶颈：最直接的思路是枚举所有切点组合（$O(2^N)$）；退一步，固定左端点后逐个右端点扫描、每次把整段排序求校验值再判断是否 $\leqslant T$，是 $O(N^2 \log N)$——$N$ 高达 $5 \times 10^5$ 时完全不可行。要提速必须回答两个问题：① 校验值能不能避开"尝试所有配对方式"、直接算出来；② 右端点能不能不逐个扫描。

观察一：校验值有闭式——排序后两端反向配对。 把 $S$ 排序为 $c_1 \leqslant c_2 \leqslant \dots \leqslant c_n$。先看选中的 $2k$ 个数内部怎么配：把它们从小到大记为 $y_1 \leqslant \dots \leqslant y_{2k}$，展开平方差——

每个选中的数在所有对里恰好出现一次，所以 $\sum a^2 + \sum b^2$ 就是这 $2k$ 个数的平方和，与配对方式无关，问题等价于让每对乘积之和 $\sum ab$ 最小。把最小数 $y_1$ 所在的对与含最大数 $y_{2k}$ 的对重新搭配：设原来 $y_1$ 配 $y_j$、$y_i$ 配 $y_{2k}$（$j < 2k$，两对不同），改配后乘积和的变化为

即把 $y_1$ 与 $y_{2k}$ 配成一对不会更差；对剩下的 $2k - 2$ 个数递归同样的论证，每对都是最小配最大：$y_1$ 配 $y_{2k}$、$y_2$ 配 $y_{2k-1}$、……、$y_k$ 配 $y_{k+1}$。再看选哪些数：在此配对下目标为 $\sum_{i=1}^{k} (y_{2k-i+1} - y_i)^2$，逐槽位交换——最大端若没取到全段最大值 $c_n$，把它换成 $c_n$ 只会让对应那一对的差变大（其余对不动）；同理最小端必取 $c_1$，依次归纳，次大端取 $c_{n-1}$、次小端取 $c_2$……每个槽位都取极端值。于是

即最小的 $k$ 个与最大的 $k$ 个反向配对。一次排序 + 三段乘积求和即可求出校验值，样例表正是这样算出来的。

观察二：段越长，校验值不减。 往集合里加一个元素 $x$：若已有 $|S| \geqslant 2M$，$S$ 的最优 $M$ 对在新集合里依旧合法，而对数仍是 $M$，最大值不会变小；若 $|S| < 2M$ 且对数不变，原配对原样合法；若对数从 $k$ 增到 $k+1$（$|S|$ 为奇数），原配对只覆盖 $2k = |S|-1$ 个数，落单的旧元素与 $x$ 补成新的一对，贡献 $\geqslant 0$。固定左端点向右扩展就是不断加元素，所以谓词 P(r) = $ "V(A[\text{left}…r]) \leqslant T$" 前真后假，可以二分。

倍增先定位，再二分收尾。 直接在 $[1, N]$ 上二分，每次验证的长度都是 $\Theta(N)$，对大量短段是巨大浪费；所以从左端点出发按长度 $1, 2, 4, 8, \dots$ 倍增验证，直到失败或越界，再在最后一个可行长度与第一个失败长度之间二分。样例 $T = 49$、左端点 0（剩余长度 5）的搜索轨迹：

两次倍增只用两段短验证就把候选范围压到 $lo = 4$ 的邻域，二分再验一次即收束：lo 全程是已验证可行的长度、hi 只会收缩，最终 $lo = hi$ 就是最长可行段长，验证次数是 $O(\log L)$ 而不是逐个扫描的 $O(L)$。

二分的下界是单元素段：$k = 0$、校验值 $0 \leqslant T$，永远可行；每次验证先切片、原地排序，再按闭式用三段 map(mul, ...) 求和（$a^2 + b^2 - 2ab$ 展开，乘加全走 C 层循环）。

贪心正确性。 设当前左端点的最长可行右端点为 $r$：任何切法的第一段右端点 $r' \leqslant r$（否则与最长性矛盾），把任意最优解的第一段右端点替换为 $r$ 仍然合法，剩余后缀规模不增；对后缀归纳，即得"每次都取最长可行段"的贪心给出最少段数。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:25
# update_at: 2026-10-01 11:25

import sys
from operator import mul

INPUT = sys.stdin.buffer


def get_value(seg: list[int], m: int) -> int:
    """段的校验值：排序后最小的 k 个与最大的 k 个反向配对，平方差之和。

    k = min(m, len(seg)//2)。平方差之和用 (a²+b²-2ab) 展开，
    三段求和都走 map(mul, ...) 的 C 层循环，避免 Python 逐对循环。
    """
    seg.sort()
    k = min(m, len(seg) >> 1)
    small = seg[:k]
    large = seg[len(seg) - k:]  # 不能写 seg[-k:]：k=0 时它等于整段
    large.reverse()             # 第 i 小配第 i 大
    return (
        sum(map(mul, small, small))
        + sum(map(mul, large, large))
        - 2 * sum(map(mul, small, large))
    )


def solve() -> None:
    cases = int(INPUT.readline())
    out: list[str] = []

    for _ in range(cases):
        n, m, limit = map(int, INPUT.readline().split())
        A = list(map(int, INPUT.readline().split()))

        # 贪心从左到右切段：每段尽量长（前缀校验值随长度单调不减）。
        segments = 0
        left = 0
        while left < n:
            span = n - left
            lo, hi = 1, 2  # 单元素段校验值为 0，必可行
            # 倍增：长度 2,4,8,... 验证到失败或越界，lo 恒为已知可行长度
            while hi <= span and get_value(A[left:left + hi], m) <= limit:
                lo = hi
                hi <<= 1
            hi = min(hi, span)
            # 二分：在 (lo, hi] 内找最长可行长度
            while lo < hi:
                mid = (lo + hi + 1) >> 1
                if get_value(A[left:left + mid], m) <= limit:
                    lo = mid
                else:
                    hi = mid - 1
            left += lo
            segments += 1

        out.append(str(segments))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:17
 * update_at: 2026-10-06 14:17
 */
// main.cpp：贪心切最少段 + 倍增定位 + 二分收尾，每段校验值用「排序后最小 k 个配最大 k 个」闭式计算。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAXN = 500005;

ll a[MAXN];   // 输入的数列 A，0 基下标
ll buf[MAXN]; // 校验值计算用的临时缓冲区：把待验证的段拷进来再排序

ll n, m, limit;

// 计算 a[left .. left+len-1] 的校验值。
// 排序后取最小的 k 个与最大的 k 个反向配对，k = min(m, len/2)，
// 校验值 = 各对差的平方之和；这就是「每对差的平方之和最大」的闭式。
ll calc_value(ll left, ll len) {
    for (ll i = 0; i < len; i++) {
        buf[i] = a[left + i];
    }
    sort(buf, buf + len);
    ll k = min(m, len / 2);
    ll res = 0;
    for (ll i = 0; i < k; i++) {
        ll d = buf[len - 1 - i] - buf[i];
        res += d * d;
    }
    return res;
}

// 从 left 出发，贪心地取最长可行段：先按长度 1,2,4,... 倍增验证，
// 失败后再在「最后可行长度」和「首个失败长度」之间二分，确定段长。
ll longest_segment(ll left) {
    ll span = n - left;
    ll lo = 1; // lo 恒为已验证可行的段长（单元素段校验值为 0，必可行）
    ll hi = 2;
    while (hi <= span && calc_value(left, hi) <= limit) {
        lo = hi;
        hi <<= 1;
    }
    if (hi > span) {
        hi = span;
    }
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        if (calc_value(left, mid) <= limit) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return lo;
}

void solve() {
    ll kase;
    cin >> kase;
    while (kase--) {
        cin >> n >> m >> limit;
        for (ll i = 0; i < n; i++) {
            cin >> a[i];
        }
        ll segments = 0;
        ll left = 0;
        while (left < n) {
            left += longest_segment(left);
            segments++;
        }
        cout << segments << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

get_value 就是观察一的闭式（注意"最大的 $k$ 个"取 seg[len(seg) - k:] 而非 seg[-k:]，因为 $k=0$ 时 seg[-0:] 等于整段）；solve 的主循环是"贪心切段"，段内先倍增后二分，lo 恒为已知可行长度、hi 先截到剩余长度，结束时 left += lo 直接跳到下一段起点。

复杂度

设一段长度为 $L$：倍增与二分各做 $O(\log L)$ 次验证，每次验证排序 $O(L \log L)$，故每段 $O(L \log^2 L)$，对所有段求和不超过 $O(N \log^2 N)$；读入数组外只需每次验证的临时切片，额外空间 $O(N)$。这与《算法竞赛进阶指南》标准 C++ 解法（倍增 + 排序检验 + 二分）同阶。Python 侧常数偏大：OJ 限时 1000 ms，本解法在本地最大一份数据约 4 s，按 python-oj-short 约定允许 TLE；热路径已用 map(mul, ...) 与原地 sort() 压缩常数，真实数据 10 组全部输出一致。

总结

• 校验值不必枚举配对方式：排序后最小的 $k$ 个配最大的 $k$ 个（$k = \min(M, \lfloor n/2 \rfloor)$），闭式 $\sum_{i=1}^{k} (c_{n-i+1} - c_i)^2$，一次排序即得。
• 集合只增不减时校验值单调不减，"前缀 $\leqslant T$"是前真后假的谓词——这把"逐个扫右端点"换成倍增 + 二分。
• 单调谓词下贪心取最长可行段即为最少段数；整体时间 $O(N \log^2 N)$、空间 $O(N)$。