记一次Sphere OJ踩坑（二分搜索的应用）

题目地址：Aggressive cows

题目大意：

将牛安排到牛圈里，求出安排方案使得离得最近的两头牛距离最远，求该距离的最大值

思路：

使用二分搜索,最大距离在[0，MAX_DISTANCE]之间，所以在此区间搜索满足条件的最大值即可，区间右端点取值很重要，可取最远的一个牛圈的距离，可以直接INT_MAX,注意不要随便来个#define inf 9999,血淋林的教训！。
代码：

#include<bits/stdc++.h> 
using namespace std;
//计算两个牛相距得最小距离的最大值 
int cowp[100003];


bool PC(int n,int c,int dis)     //检查是否能将c头牛以dis的间距放在n个圈里 
{
    int i,cnt = 1,front = 0;
    for(i = 1;i < n; i++) 
    {
        if(cowp[i] - cowp[front] >= dis) 
        {
            cnt++;
            front = i;
        }
    }
    return cnt >= c;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int i,N,C;
        cin >> N >> C;
    
        for(i = 0;i < N; i++)   scanf("%d",&cowp[i]);
        
        sort(cowp,cowp+N);
        
        int lb = 0,ub = cowp[N-1],mid;
        while(ub - lb > 1)  
        {
            mid = (ub + lb) / 2;
            if(PC(N,C,mid)) lb = mid;
            else ub = mid;
        }
        
        cout << lb << endl;         //返回能放下的最大距离 
        
    }
}