农夫约翰建造了一座有 n 间牛舍的小屋，牛舍排在一条直线上，第 i 间牛舍在 xi​ 的位置，但是约翰的 m 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入格式

第一行用空格分隔的两个整数 n 和 m；

第二行为 n 个用空格隔开的整数，表示位置 xi​。

输出格式

一行一个整数，表示最大的最小距离值。

输入输出样例

输入 #1复制

5 3
1 2 8 4 9

输出 #1复制

3

说明/提示

【样例解析】把牛放在 1，4，8 这三个位置，距离是 3。容易证明最小距离已经最大。

【数据范围】对于 100% 的数据，2≤n≤105，0≤xi​≤109，2≤m≤n。不保证 x 数组单调

#include<iostream>

#include<algorithm>

using namespace std;

int n,m;

int pl[100005]; //pl是place的缩写

void init(){

    ios::sync_with_stdio(false); //读入数据较多，关闭读写同步以加快读写速度

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        cin>>pl[i];

    }

    sort(pl+1,pl+n+1); //对奶牛的需求排序

}

bool check(int x){

    int num=1,lasth=1; //上一次放牛的房子编号

    for(int i=2;i<=n;i++){

        if(pl[i]-lasth>=x){ //可以放牛

            lasth=pl[i];

            num++;

        }

    }

    return num>=m; //返回值的压行技巧

}

int main(){

    init();

    //接下来是二分答案的模板

    int l=1,r=1e9,ans,mid;

    while(l<=r){

        mid=(r-l)/2+l; //防止爆long long的小技巧

        if(check(mid)){

            ans=mid; //暂时存答案

            l=mid+1;

        }

        else{

            r=mid-1;

        }

    }

    cout<<ans;

return 0;

}