基本思路：从最左段开始，每次将右端点尽量大地往右放。

伪代码类似这样：

l = 1
cnt = 0
while l <= n
    l = jump(l) + 1 // jump(l) 即 r
    cnt = 1
print cnt

另外还需要 check 函数检验 是否符合题意

现在考虑 函数的实现

jump 函数 实现方法 1

枚举法，伪代码类似这样：

function jump(l) // ver 1
    r = l
    while check(l, r) == true && r <= n
        r++;
    return r

check 函数 实现方法 1

暴力法，伪代码类似这样：

function check(l, r) // ver 1
    sort(l, r)
    cnt = 1
    tot = 0;
    while cnt <= m && l <= r
        tot += pow(p[l] - p[r], 2)
    return tot <= k

复杂度：

使用 jump(ver 1) 与 check(ver 1)

复杂度：
炸完，没试过，但肯定 TLE （除非 ）

jump 函数 实现方法 2

考虑二分寻找 ，伪代码类似这样：

function jump(l) // ver 2
    L = l, R = n, r = l
    while L <= R
        mid = (L + r) / 2
        if check(l, mid) L = mid + 1, r = mid
        else R = mid - 1
    // 不同人二分实现方式可能略有不同
    return r

使用 jump(ver 2) 与 check(ver 1)

复杂度：
卡的很紧，亲测 45pts，也许 松排 可以过

jump 函数 实现方法 3

考虑倍增寻找 ，伪代码类似这样：

function jump(l) // ver 3
    p = 1
    r = l
    while p != 0 && r <= n
        if check(l, r + p) r += p, p *= 2;
        else p /= 2
    return r

使用了类似二进制优化的思想，当 较小的时候略去了大量无用的判断，有优化作用。

使用 jump(ver 3) 与 check(ver 1)

复杂度：也是 但实际效果比 jump(ver 2) 好得多
data#8 比较大，亲测 91pts，松排 肯定可以过，但完全没必要

check 函数 实现方法 2

配合 jump(ver 3) 食用

考虑每次 check(l, r + p) 的时候， 区间事实上是已经排好序的，可以加以利用。
考虑仅对 排序，然后 类似归并排序地合并 与

伪代码类似这样

function check(l, r, newR) // ver 2
    sort(r + 1, newR)
    merge([l, r], [r + 1, newR])
    cnt = 1
    tot = 0;
    while cnt <= m && l <= r
        tot += pow(p[l] - p[r], 2)
    return tot <= k

注意：如果 check 返回 false，应当还原 至上一状态（上次 check 后，本次 check 的归并前）否则 的数据就不能被下一次所利用。

使用 jump(ver 3) 与 check(ver 2)

复杂度：也是
过 data#8 毫无压力，亲测 977ms，不到时限的一半。

代码

已略去头文件 & I/O优化

//     自己选择的路，跪着也要走完。朋友们，虽然这个世界日益浮躁起来，只
// 要能够为了当时纯粹的梦想和感动坚持努力下去，不管其它人怎么样，我们也
// 能够保持自己的本色走下去。                               ——陈立杰
/*************************************
 * @problem:      3758: 0601 Genius ACM.
 * @user_id:      1677.
 * @user_name:    zhaoyi20(brealid).
 * @time:         2020-06-01.
 * @language:     C++.
 * @upload_place: XOJ.
*************************************/ 

const int N = 500007;
int T, n, m; int64 k;
int p[N], tmp[N], tmpMerge[N], save[N];

void merge(int p1, int e1, int p2, int e2) {
    int p = p1, it = p1;
    while (p1 <= e1 && p2 <= e2) {
        if (tmp[p1] < tmp[p2]) tmpMerge[p++] = tmp[p1++];
        else tmpMerge[p++] = tmp[p2++];
    }
    while (p1 <= e1) {
        tmpMerge[p++] = tmp[p1++];
    }
    while (p2 <= e2) {
        tmpMerge[p++] = tmp[p2++];
    }
    while (it <= e2) {
        tmp[it] = tmpMerge[it];
        it++;
    }
}

bool check(int l, int mid, int r) {
    r = min(r, n);
    for (int i = mid + 1; i <= r; i++) tmp[i] = p[i];
    sort(tmp + mid + 1, tmp + r + 1);
    merge(l, mid, mid + 1, r);
    int64 ans(0);
    for (int i = 1, p = l, q = r; i <= m && p < q; i++, p++, q--) {
        ans += (int64)(tmp[p] - tmp[q]) * (tmp[p] - tmp[q]);
        if (ans > k) return false;
    }
    return true;
}

signed main() {
    T = read<int>();
    while (T--) {
        n = read<int>();
        m = read<int>();
        k = read<int64>();
        for (int i = 1; i <= n; i++) p[i] = read<int>();
        int cnt = 0;
        for (int l = 1, r, kth; l <= n; l = r + 1) {
            kth = 1; r = l;
            tmp[l] = p[l];
            while (kth && r <= n) {
                for (int i = l; i <= r; i++) save[i] = tmp[i];
                if (check(l, r, r + kth)) r += kth, kth <<= 1;
                else {
                    kth >>= 1;
                    for (int i = l; i <= r; i++) tmp[i] = save[i];
                }
            }
            cnt++;
        }
        write(cnt, 10);
    }
    return 0;
}

// Create File Date : 2020-06-01