天才ACM

思路：倍增枚举分段即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+50;
int n,m,k;
int ans;
int a[N],s[N];
int sq(int x){
    return x*x;
}
int check(int l,int r){
    int idx=0;
    for(int i=l;i<r;i++){
        s[idx++]=a[i];
    }
    sort(s,s+idx);
    int sum=0;
    for(int i=0;i<m&&i<idx;i++,idx--){
        sum+=sq(s[i]-s[idx-1]);
    }
    return sum;
}
signed main(){
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m >> k;
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        ans=0;
		int bg=0,ed=0;
        while(ed<n){// 纯纯的倍增
            int cd=1;
            while(cd){
                if(ed+cd<=n&&check(bg,ed+cd)<=k){
                    ed+=cd;
                    cd<<=1;
                }else cd>>=1;
            }
            bg=ed;
            ans++;
        }
        cout << ans << endl;
    }
}