给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:
从集合 S 中取出 M 对数(即 2∗M 个数，不能重复使用集合中的数，如果 S 中的整数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 S 的“校验值”。
现在给定一个长度为 N 的数列 A 以及一个整数 T。
我们要把 A 分成若干段，使得每一段的“校验值”都不超过 T。
求最少需要分成几段。
看见“使得平方之和最大”、“最少需要分成几段”就能发现该题是求解最大最小问题，最开始想到的就应该是二分查找，二分查找是解决最大最小问题最常用的办法。
对于差的平方之和最大，我们可以证明，将最大与最小做差的平方+次大次小做差的平方+···，此时的差的平方之和最大，可以用多项式展开来证明。并且M对数的数量是不定的，因此排序算法是不可避免的。
综上，我们应该用二分来确定每一段的长度，若分成n段则最坏时间复杂度在
O
(
n
)
O(n)
O(n)，每段又要调用
O
(
l
o
g
n
)
O(logn)
O(logn)次二分，在每次二分又要用排序算法进行求解
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。所以总的算法复杂度在
O
(
n
2
l
o
g
2
n
)
O(n^{2}log^{2}n)
O(n2log2n)，但经过严谨的数学证明应该是
O
(
n
2
l
o
g
n
)
O(n^{2}logn)
O(n2logn)。
除了二分以外是否有更好的方法来减低时间复杂度，解决这个问题呢？那就是“倍增”，考虑如下问题
对于给定一个正整数数列，已知其前缀和，如何快速求出从哪位元素开始，之前的所有元素总和大于sum。
这题我们就可以用前缀和的思想来解决，常规方法可能是用二分，但一定会耗费 l o g n logn logn的时间。如果用朴素算法，则更需要 n n n的时间。如果我们在朴素算法上进行改进，遍历前缀和的时候步长是动态变化的，而不是固定为1，遵循以下规则：
相比于二分查找的好处就是，倍增在最差的情况下也才需要 O ( l o g n ) O(logn) O(logn)的时间，而假如所求解越靠近队首，求解时间越短，平均时间复杂度要优于二分。
因此我们考虑用倍增来进一步优化求解，如果使用倍增，那么我们的时间复杂度可以降低为
O
(
n
l
o
g
2
n
)
O(nlog^{2}n)
O(nlog2n)，表示成如下图：
如果最终结果要分成3段，长度分别是len1、len2和len3，那么在每一段，我们倍增查找用时就是
O
(
l
o
g
l
e
n
1
)
O(loglen1)
O(loglen1)，排序用时就是
O
(
l
e
n
1
l
o
g
l
e
n
1
)
O(len1loglen1)
O(len1loglen1)，因此每一段我们总用时就是
O
(
l
e
n
1
l
o
g
2
l
e
n
1
)
O(len1log^{2}len1)
O(len1log2len1)。再将这若干段相加可以得到总的时间复杂度
O
(
n
l
o
g
2
n
)
O(nlog^{2}n)
O(nlog2n)，相比于二分要降低很多。
接下来，我们考虑进一步的优化。在上面的方法中，我们每倍增一段，就要重新计算整个区间的排序，可不可以利用归并排序的方法，当倍增一段，我们只计算倍增这一区间的排序，然后在利用之前的计算结果归并，这样的话就省去重复计算。
我们来看一下这样的时间复杂度，仍然以上图为例，假设最终结果分成3段，每一段排序的用时就是
O
(
l
e
n
1
l
o
g
l
e
n
1
)
O(len1loglen1)
O(len1loglen1)，那么归并用时需要多久呢？我们知道每一段要进行
O
(
l
o
g
l
e
n
1
)
O(loglen1)
O(loglen1)的时间，在这些时间里，我们要进行长度为1、2、4、8、······、2len1长度的归并排序，因此归并用时就是这些长度的累加和，利用等比数列求和可知结果是
O
(
l
e
n
1
)
O(len1)
O(len1)的，所以每一段的用时就是
O
(
l
e
n
l
o
g
l
e
n
+
l
e
n
)
O(lenloglen + len)
O(lenloglen+len)，总用时就是各段用时相加，依旧是
O
(
n
l
o
g
n
+
n
)
O(nlogn + n)
O(nlogn+n)。至此，我们明确了该题的最优解法。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500010;
//n表示集合元素个数，t表示校验值，a、b、temp用来做排序运算，m是对数，res是结果
ll n, t, a[N], b[N], temp[N];
int m, res;
ll check(int start, int end, int test){
//start表示当前要求解段的起始位置，end是当前小于校验值的结尾，test是要尝试的结尾
//因为我们要对a数组进行排序，所以a数组end到test的顺序有可能之前已经被打乱，要拷贝b数组（原始数据）的内容
for(int i=end + 1; i<=test; i++) a[i] = b[i];
sort(a + end + 1, a + test + 1);
//双指针归并
int f = start, b = end+1;
//sum是最终这一段的校验值
ll sum = 0;
for(int i=start; i<=test; i++){
if(b > test || f <= end && a[f]<a[b]) temp[i] = a[f++];
else temp[i] = a[b++];
}
for(int i=0; i<(test-start+1>>1) && i<m; i++){
sum += (temp[start+i]-temp[test-i]) * (temp[start+i]-temp[test-i]);
}
return sum;
}
void solve(){
//start表示当前要求解段的起始位置，end是当前小于校验值的结尾，l是倍增长度
int start = 0, end = 0, l;
while(start < n){
l = 1;
//如果倍增长度等于0，即收敛
while(l){
if(end + l >= n || check(start, end, end + l) > t) l >>= 1;
else{
// 当前end+l结尾可以满足条件，那么我们就将之前排好的序保存下来，方便下次使用
for(int i=start; i<=end+l; i++) a[i]=temp[i];
end = end + l;
l <<= 1;
}
}
//开始下一段的寻找
start = ++end;
res++;
}
}
int main(){
//k表示测试集组数
int k;
cin >> k;
while(k--){
cin >> n >> m >> t;
for(int i=0; i<n; i++){
cin >> a[i];
b[i] = a[i];
}
res = 0;
solve();
cout << res << endl;
}
return 0;
}