分析

我们可以考虑一个合法答案 ，那么 ，则 也是一个合法答案。那么这个满足单调性，我们可以考虑二分，如何判断 是否是一个合法解。我们考虑贪心，从左向右考虑，每次考虑最靠左而且没有被现在的区间覆盖的点。对于这个点也可以二分，好像直接做也没有问题。那么最后判断是否 就可以了。

• 代码中所有二分的地方，我都换成了倍增。感觉还是非常快的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10000,inf = 0x3f3f3f3f;
int a[N],n,K,Log[N];
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int find(int l,int r,int val) {
    int ans = l;
    if(a[l] > val) return l;if(a[r] <= val) return -1;
    for(int i = Log[r - l + 1];~i;i--) {
        if((a[ans + (1 << i)] <= val) && ((ans + (1 << i)) <= r)) ans += (1 << i);
    }
    return ans + 1;
}
bool check(int x) {
    int pos = -inf,m = 0,now = 1;
    while(now <= n) {
        now = find(now,n,pos + x);
        if(now == -1) return m <= K;
        m++;pos = a[now] + x;now = now + 1;
    }
    return m <= K;
}
int main() {
    n = read();K = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
    sort(a+1,a+1+n);
    int ans = 1 << 30;
    for(int i = 30;~i;i--) {
        if(check(ans - (1 << i))) ans -= (1 << i);
    }
    printf("%d\n",ans);
    return 0;
}