分析

题目中说的最小的满足值，那么就是二分答案
Check:每次贪心当两个端点距离小于Mid时就增加一段
即可

代码

//P6174
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=5e4+10;

LL Total,Limit;
LL Num[MaxN];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline bool Check(LL Temp) {
    LL Sum=0,L=1,R=1,Cnt=0;
    for(;L<=Total;L=R+1,R=L) {
        while(R<Total && Num[R+1]-Num[L]<=2*Temp) R++;
        Cnt++;
    }
    return Cnt<=Limit;
}

signed main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Total>>Limit;
    FOR(i,1,Total) { cin>>Num[i]; }
    sort(Num+1,Num+Total+1);
    LL L=0,R=(Num[Total]-Num[1])>>1,Ans=(Num[Total]-Num[1])>>1;
    while(L<=R) {
        LL Mid=(L+R)>>1;
        if(Check(Mid)) { Ans=Mid; R=Mid-1; }
        else { L=Mid+1; }
    }
    cout<<Ans<<endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}