借书

借书 (二分 \(\star\))

• \(Dilhao\) 一共有 \(n\) 本教科书，每本教科书都有一个难度值，他每次出题的时候都会从其中挑两本教科书作为借鉴，如果这两本书的难度相差越大，\(Dilhao\) 出的题就会越复杂，也就是说，一道题的复杂程度等于两本书难度差的绝对值。
• 这次轮到 \(ldxxx\) 出题啦，他想要管 \(Dilhao\) 借 \(m\) 本书作为参考去出题，\(Dilhao\) 想知道，如果 \(ldxxx\) 在 \(Dilhao\)给出 的\(m\) 本书里挑选难度相差最小的两本书出题，那么 \(ldxxx\) 出的题复杂程度最大是多少？

Input

• 第一行是 \(n\) 和 \(m\)。
• 接下来的 \(n\) 行，每行一个整数 \(a_i\) 表示第 \(i\) 本书的难度。

Output

• 一个整数为 \(ldxxx\) 出的题复杂程度的最大值。

Sample Input

6 3 
5
7
1
17
13
10

Sample Output

7

Hint

• 样例解释：\(Dilhao\) 给了 \(ldxxx\) 难度为 \(1,10,17\) 的三本书，\(ldxxx\) 挑选难度为 \(10\) 和 \(17\) 的两本书，出题复杂度为 \(7\)；
• 如果 \(Dilhao\) 给出其他任何三本书，其中的两本书难度差的最小值都小于 \(7\)，所以 \(ldxxx\) 出题最大的复杂程度为 \(7\)。
• 对于 \(30\%\) 的数据： \(2<=n<=20\)；
• 对于 \(60\%\) 的数据： \(2<=n<=1000\)；
• 对于 \(100\%\) 的数据： \(2<=n<=100000， 2<=m<=n， 0<=a_i<=1000000000\)。
• 来源：

分析

• \(2<=n<=100000\) 最小值最大？暗示二分。我们可以先二分出一个最小值，然后检验这个最小值的合法性。那么怎么检验合法性呢？
• 我们发现只要在满足二分出来的答案的情况下能选出来大于等于 \(m\) 个数这个答案就一定是合法的。那么我们应该怎么取数呢？先将m个数排序，我们想要取出来的符合条件的数尽可能多，为了让一个数跟之前选择的数的差尽可能大，我们一定是希望前面的选择的数尽可能的小，前面选小的数一定不会让答案变的更劣，所以我们先选择最小的第一个数，依次往下扫描每一个数，只要和上一个选择的数的差大于二分答案就选。

Code

#include <bits/stdc++.h>
const int maxn=1e5+5;
int n,m,a[maxn],cf[maxn];
int Max=0;
void Init(){
    scanf("%d%d",&n,&m);    
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        Max=std::max(Max,a[i]);
    }
    std::sort(a+1,a+n+1);
    for(int i=1;i<n;i++){
        cf[i]=a[i+1]-a[i];//cf差分数组
    }
}
bool check(int x){
    int cnt=0,ch=0;//ch当前的最大差值
    for(int i=1;i<n;i++){
        ch+=cf[i];
        if(ch>=x){//找到一对差值大于x
            cnt++,ch=0;//从下个位置找下一对
        }
    }
    if(cnt>=m-1)
        return true;
    return false;
}
void Solve(){
    int l=0,r=Max;
    while(l<=r){
        if(r-l==1){
            if(check(r)==true)
                l=r;
            break;
        }
        int mid=(l+r)/2;
        if(check(mid)==true)
            l=mid;
        else
            r=mid;
    }
    printf("%d\n",l);
}
int main(){
    Init();
    Solve();    
    return 0;
}