1433：【例题1】愤怒的牛

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 603 通过数: 333

【题目描述】

农夫 John 建造了一座很长的畜栏，它包括N (2 ≤ N ≤ 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 ≤ xi ≤ 1,000,000,000). 但是，John的C (2 ≤ C ≤ N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢

【输入】

第一行：空格分隔的两个整数N和C；

第二行---第N+1行：i+1行指出了xi的位置。

【输出】

一个整数，最大的最小值。

【输入样例】

5 3
1 2 8 4 9

【输出样例】

【提示】

把牛放在1，4，8这样最小距离是3

思路：

先排序，然后从0到x[n]-x[1]二分检查正确答案右边界；

因为d<=右边界可以放m头牛，d取r为最大值

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+3;
int n,m,x[N];
inline bool check(int d){
    //以d为答案，看是否正确 
    int cow=1;
    int rgt=x[1]+d;
    for(int i=2;i<=n;i++){
        if(x[i]<rgt) continue;
        //不符合跳过 
        ++cow;
        rgt=x[i]+d;
        //符合计数并更新rgt 
    }
    return cow>=m;
    //cow>=m是成立 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>x[i];
    sort(x+1,x+1+n);
    //二分查找 
    int l=0,r=x[n]-x[1];
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}