8688 进击的奶牛

描述

Farmer John 建造了一个有 N（2≤N≤105) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x1​,x2​,⋯,xN​（0≤xi​≤109）。

他的 C（2≤C≤N）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入描述

第 1 行：两个用空格隔开的数字 N 和 C。

第 2∼N+1 行：每行一个整数，表示每个隔间的坐标。

输出描述

输出只有一行，即相邻两头牛最大的最近距离。

样例输入 1 

5 3
1
2
8
4
9

样例输出 1 

3

c++代码

#include <iostream>
#include <algorithm> 
using namespace std;
const int N=1e5+5;
int n,m,a[N];
 
int check(int x){
    int cnt=1,p=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]-p>=x) p=a[i],cnt++; 
    }
    if(cnt>=m) return 1;
    else return 0; 
}
int 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+n+1);
    int l=1,r=a[n];
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}