这道题用二分的话，复杂度是 $O(n \log^2 n)$ 的，能否消一个 $\log$？

下面附上 Code，思路大概就是二分找这个点最多能向后再选几个点，然后 $O(n \log n)$ 地 check。

#include<bits/stdc++.h>
// #pragma G++ optimize(2)
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
const int N=5e5+5;
int n,m;
ll k,a[N],b[N];
bool check(int l,int r) {
	for(int i=l;i<=r;i++) b[i]=a[i];
	sort(b+l,b+r+1);
	ll tmp=0;
	for(int i=1;i<=m;i++) {
		int x=l+i-1,y=r-i+1;
		if(x>=y||x>r||y<l) break;
		tmp+=(b[y]-b[x])*(b[y]-b[x]);
	}
	// cout<<"l="<<l<<" r="<<r<<" tmp="<<tmp<<"\n";
	return tmp<=k;
}
int calc(int pos) {
	int l=pos,r=n,res=l;
	while(l<=r) {
		int mid=(l+r)/2;
		if(check(pos,mid)) {
			res=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	return res;
}
void solve() {
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=1,ans=0;
	while(l<=n) {
		// cout<<"l="<<l<<"\n";
		l=calc(l)+1;
		ans++;
	}
	cout<<ans<<"\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--) solve();
	return 0;
}