分段校验值问题

题目描述

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

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

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

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

求最少需要分成几段。

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

2
1

限制条件

• $1 \le K \le 12$
• $1 \le N, M \le 500000$
• $0 \le T \le 10^{18}$
• $0 \le A_i \le 2^{20}$

样例解释 #1

第一组测试数据

$N = 5, M = 1, T = 49$

数列：$[8, 2, 1, 7, 9]$

要使“每对数的差的平方”之和最大，应该取最大值和最小值组成一对：

• 排序后：$[1, 2, 7, 8, 9]$
• 最大差：$9 - 1 = 8$
• 差的平方：$8^2 = 64$

$64 > 49$，所以不能整个数列作为一段。

尝试分段：

1. 第一段：$[8, 2, 1]$，排序后 $[1, 2, 8]$，最大差 $8-1=7$，$7^2=49$，校验值 $=49 \le 49$，符合
2. 第二段：$[7, 9]$，排序后 $[7, 9]$，最大差 $9-7=2$，$2^2=4$，校验值 $=4 \le 49$，符合

最少需要分成 $2$ 段。

第二组测试数据

$N = 5, M = 1, T = 64$

同样数列：$[8, 2, 1, 7, 9]$

整个数列的校验值为 $64$，$64 \le 64$，所以整个数列作为一段即可。

最少需要分成 $1$ 段。

校验值计算方法

对于集合 $S$，要使得 $M$ 对数的差的平方之和最大：

1. 将集合 $S$ 中的数排序
2. 取最小的 $M$ 个数和最大的 $M$ 个数配对（如果元素个数 $< 2M$，则取全部）
3. 计算 $(最大-最小)^2$ 的和

具体来说：

• 设排序后的序列为 $a_1, a_2, \dots, a_k$（$k$ 为集合大小）
• 如果 $k \ge 2M$，则校验值 = $\sum_{i=1}^M (a_{k-i+1} - a_i)^2$
• 如果 $k < 2M$，则校验值 = $\sum_{i=1}^{\lfloor k/2 \rfloor} (a_{k-i+1} - a_i)^2$