C++ 代码
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#define sqr(a) (a)*(a)
typedef long long ll;
using namespace std;
const int N = 5e5 + 5;
int k, n, m, ans; //a是保存排序后的数组 b是merge后的数组 rec是保存原序列
ll t, rec[N], a[N], b[N];
void merge(int L, int mid, int r) {
int i = L, j = mid + 1;
for (int k = L; k <= r; k++) {
if (j > r || i <= mid && a[i] <= a[j]) {
b[k] = a[i++];
} else {
b[k] = a[j++];
}
}
}
//检查这一段是否符合要求
bool check(int L, int mid, int r) {
//【L, mid - 1】之前的一段 【mid, r】是新增的一段
for (int k = mid; k <= r; k++) {
//将原序列放入a中 进行排序
a[k] = rec[k];
}
sort(a + mid, a + r + 1);
//将2段进行合并
//为什么是mid-1 因为我们前面一段结尾是mid-1
merge(L, mid - 1, r);
ll sum = 0;
for (int k = 1; k <= ((r - L + 1) >> 1) && k <= m; k++) {
//求校验值
sum += sqr(b[r - k + 1] - b[L + k -1]);
}
if (sum <= t) {
//进行a数组还原 只有这一段成功了才进行还原
for (int k = L; k <= r; k++) a[k] = b[k];
return true;
} else {
return false;
}
}
void f() {
//p是倍增的长度
int p = 1, L = 1, r = 1;
a[L] = rec[L];
while (r <= n) {
if (!p) {
//代表已经选够了一段
ans++;
L = ++r;
//将新的一段第一个值进行赋值
a[L] = rec[L];
//将长度恢复为1
p = 1;
} else if (r + p <= n && check(L, r + 1, r + p)) {
//更新l和r
r = r + p;
p <<= 1;
} else {
//倍增长度减少为一半
p >>= 1;
}
}
}
int main() {
scanf("%d", &k);
while (k--) {
scanf("%d%d%lld", &n, &m, &t);
for (int i = 1; i <= n; i++) {
scanf("%lld", rec + i);
}
ans = 0;
f();
printf("%d\n", ans);
}
return 0;
}
%
大佬牛皮