题解|#Aggressive cows #（二分法）

Aggressive cows（https://oj.youdao.com/problem/1596?from=problems）

题目描述

农夫 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的位置

输出描述

第一行：一个整数，最大的最小值

#include<iostream>
#include<algorithm>
using namespace std;
int room[100010];

bool distance(int x,int n,int c){//判断x能否作为最小距离
    int s=room[0];
    c--;
    for(int i=1;i<n;i++){
        if(room[i]-s<x)continue;
        else{
            s=room[i];//更新结点位置
            c--;//放牛
            if(c==0)return true;
        }
    }
   
    return false;
    
}

int main(){
    int n,c;
    while(scanf("%d",&n)!=EOF){
        scanf("%d",&c);
        for(int i=0;i<n;i++){
            scanf("%d",&room[i]);
        }
        sort(room,room+n);//二分法一定要先排序
        int left=1;
        int right=room[n-1]-room[0];
        while(left<=right){
            int middle=left+(right-left)/2;
            if(distance(middle,n,c))left=middle+1;//满足条件middle左边舍去
            else right=middle-1;//不满足条件middle右边舍去
        }
        printf("%d\n",right);
        
    }
    return 0;
}