0x00基本算法（0x06 倍增）例题1：天才ACM

P10455 Genius Acm

【题意】

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

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

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

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

求最少需要分成几段。

【输入格式】

第一行一个整数 $T \ (1 \le T \le 12)$，代表有 $T$ 组数据。每组数据描述如下：

第一行三个整数 $N \ M \ K \ (1≤N,M≤5 \times 10^5, 0 \le T \le 10^{18})$。

下来 $N$ 个整数 $A_i \ (0 \le Ai \le 2^{20})$。

【输出格式】

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

【输入样例】

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

【输出样例】

2
1