博客地址：https://blog.csdn.net/qq_61935738/article/details/125461607?spm=1001.2014.3001.5502
/*
大概思路：
使用倍增的方法先求出区间[L, L + len]的校验值
若成立则令L += len , len <<= 1
若不成立则令len >>= 1直到len为0循环结束
每对数的差的平方”之和最大因此要使它最大则应该是
最小的数与最大的数配对，次小的数与次大的数配对
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 500010;
LL T;
int n, m;
int a[N], temp[N], t[N];
//a[N]为A数组,temp为归并排序中的临时数组, t[N]为当前正在倍增的数组
LL sq(int x)
{
return (LL)x * x;
}
bool check(int l, int mid, int r)
{
for (int i = mid; i < r; i ++ ) t[i] = a[i];//因为[l, mid)在上一轮以及被排序计算过，所以直接从mid开始
sort(t + mid, t + r);//将t的区间排序
int i = l, j = mid, k = 0;
while (i < mid && j < r)//将排好序的t放入temp中，此时temp里面的数都是从小到大排序的
{
if (t[i] < t[j]) temp[k ++ ] = t[i ++ ];
else temp[k ++ ] = t[j ++ ];
}
while (i < mid) temp[k ++ ] = t[i ++ ];
while (j < r) temp[k ++ ] = t[j ++ ];
LL sum = 0;
for (int i = 0; i < m && i < k; i ++, k -- )//检查校验值是否符合要求，题目说了校验值是
sum += sq(temp[i] - temp[k - 1]); //每对数的差的平方”之和最大因此要使它最大则应该是
//最小的数与最大的数配对，次小的数与次大的数配对
return sum <= T; //因为temp从小到大排序因此选择第一个与最后一个配对
}
int main()
{
int cnt;
cin >> cnt;
while (cnt -- )
{
scanf("%d %d %lld", &n, &m, &T);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int ans = 0, len;
int start = 0, last = 0;
while (last < n)
{
len = 1;
while (len)
{
if (last + len <= n && check(start, last, last + len))//判断[start, last + len)是否符合要求
{
last += len, len <<= 1;//若成立利用倍增思想扩大范围
if (last >= n) break;//若last >= n，则last + len比大于n + 1题解结束
for (int i = start; i < last; i ++ )//经过check后数组temp中的[start, len]以及被排序过
t[i] = temp[i - start];//将他放入倍增数组t以免重复排序
}
else len >>= 1;//若不成立缩小范围
}
start = last;//当len == 0说明该区间[start, last]已选得最大区间长度的符合要求的校验值
ans ++ ;//所以开始下一个区间的选取
}
printf("%d\n", ans);
}
}
