SOLUTION

直接二分，贪心 check 即可。

具体地，check 时直接枚举，记录上一个选的谁，看能不能选现在的，能选一定选。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
int a[101000];
int check(int mid){
    int lst=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]-mid>=a[lst]) lst=i,cnt++;
    }
    return cnt>=m;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    a[0]=-1e18;
    int L=0,R=1e9;
    while(L<R){
        int mid=(L+R+1)>>1;
        if(check(mid)) L=mid;
        else R=mid-1;
    }
    cout<<L<<'\n';
    return 0;
}