贪心、二分

观察题目，发现序列最后的极差必定是序列中某两个数的差。

假设这两个数分别为 $l,r(l<r)$，那么修改次数最小的方案只可能是：

• 将所有小于 $l$ 的数修改为全局最大值，再将所有大于 $r$ 的数修改为 $l$。
• 将所有大于 $r$ 的数修改为全局最小值，再将所有小于 $l$ 的数修改为 $r$。

修改次数是容易计算的，答案单调性显然，二分答案即可完成。

注意答案上界为 $2 \times 10^9$，计算中间点时需要防止 int 溢出。

时间复杂度 $O(n \log V)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,a[100'005];
bool fail(int x){
    int l=1,r=1;
    while(l<=n){
        while(r+1<=n&&a[r+1]-a[l]<=x) ++r;
        if(min((l-1)*2+(n-r),(n-r)*2+(l-1))<=m) return 0;
        ++l;
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int l=0,r=a[n]-a[1];
    while(l<=r){
        int mid=l+(r-l)/2;
        if(fail(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}