题目链接

https://www.acwing.com/problem/content/description/111/

题解链接

https://www.acwing.com/solution/content/15458/
写的太好了，提醒一下，第一个代码会TLE，其他两个均可以AC
我下面附上的两个代码是可以AC的。

AC代码

//非归并排序+倍增
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=5e5+10;

int n,m,T;
ll k,tmp[N],a[N];

bool check(int l,int r)
{
    int num=0;ll res=0;
    for(int i=l;i<r;i++) tmp[num++]=a[i];
    sort(tmp,tmp+num);
    for(int i=0;i<m && i<num;i++,num--)
    res+=(tmp[i]-tmp[num-1])*(tmp[i]-tmp[num-1]);
    return res<=k;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int ans=0,len=1,end=0,s=0;
        scanf("%d%d%lld",&n,&m,&k);
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        while(end<n)
        {
            len=1;
            while(len)//倍增核心 
            {
                if(end+len<=n && check(s,end+len)) end+=len,len<<=1;
                else len>>=1;    
            }
            ans++;
            s=end;
        }    
        printf("%d\n",ans);
    }    
    return 0;
}
//归并排序+倍增
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=5e5+10;

int n,m,T;
ll k,tmp[N],a[N],t[N];

bool check(int l,int mid,int r)
{
    for(int i=mid;i<r;i++) t[i]=a[i];
    sort(t+mid,t+r);

    int p=l,q=mid,num=0;ll res=0;
    while(p!=mid && q!=r)
    {
        if(t[p]<t[q]) tmp[num++]=t[p++];
        else tmp[num++]=t[q++];
    }
    while(p!=mid) tmp[num++]=t[p++];
    while(q!=r) tmp[num++]=t[q++];

    for(int i=0;i<m && i<num;i++,num--) 
    res+=(tmp[i]-tmp[num-1])*(tmp[i]-tmp[num-1]);
    return res<=k;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int ans=0,len=1,end=0,s=0;
        scanf("%d%d%lld",&n,&m,&k);
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        while(end<n)
        {
            len=1;
            while(len)//倍增核心 
            {
                if(end+len<=n && check(s,end,end+len))
                {
                    end+=len,len<<=1;
                    for(int i=s;i<end;i++)
                    t[i]=tmp[i-s];
                } 
                else len>>=1;    
            }
            ans++;
            s=end;
        }    
        printf("%d\n",ans);
    }    
    return 0;
}