Aggressive cows （二分加枚举）

http://bailian.openjudge.cn/practice/2456

农夫 John 建造了一座很长的畜栏，它包括N (2≤N≤100,000)个隔间，这
些小隔间的位置为x0,…,xN-1
(0≤xi
≤1,000,000,000,均为整数,各不相同).

John的C (2≤C≤N)头牛每头分到一个隔间。牛都希望互相离得远点省得
互相打扰。怎样才能使任意两头牛之间的最小距离尽可能的大，这个最
大的最小距离是多少呢？

问题分析

看懂题目很重要，网上关于此题的解析很多，不多赘述

算法分析

1.枚举法
（1 ) 第1头牛放在x0
（2 ) 若第k头牛放在xi ，则找到xi+1到xN-1中第一个位于[xi+D, 1,000,000,000]中的Xj
第k+1头牛放在Xj。找不到这样的Xj,则 D=D-1,转 1)再试

若所有牛都能放下，则D即答案
复杂度 1,000,000,000/C *N，即 1,000,000,000, 超时!

2.二分加枚举
先得到排序后的隔间坐标 x0,…,xN-1

在[L,R]内用二分法尝试“最大最近距离”D = (L+R)/2 (L,R初值为
[1, 1,000,000,000/C]

若D可行，则记住该D，然后在新[L,R]中继续尝试(L= D+1)
若D不可行，则在新[L,R]中继续尝试(R= D-1)

复杂度 log(1,000,000,000/C) * N

/*
二分加枚举的具体思想是
通过二分法提供最小距离D来验证该D能否安排下所有的牛
如果D能够安排下所有的牛，则最小距离的最大值比D大
如果D不可行，则最小距离的最大值比D小
判断D可行与否的函数为greedy函数

抓住和理解透彻这一点整个问题就迎刃而解了

*/ 

#include<stdio.h>
#include<algorithm>
#include<iostream>
#define N 100010
using namespace std;
int n,c; 
int x[N];

//判断d是否可行 
int greedy(int d){    
    int temp=x[0];
    int count=1;
    int i=1;            //可以改成for循环 
    while(i<n){      
        if(x[i]-temp>=d){
            temp=x[i];
            count++;
            if(count==c){
                return 1;
            }
        }
        i++;
    }
    return 0;   
} 

//二分法寻求d的最大值 
void LargestDis(){   
    int l=0,r=x[n-1]-x[0];
    int d=(l+r)/2;
    while(l<=r){
        if(greedy(d)) {
            l=d+1;
        }else{
            r=d-1;
        }
        d=(l+r)/2;
    }
    cout<<l-1;
}

//test 
int main(){
    while(scanf("%d%d",&n,&c)!=EOF){
        for(int i=0;i<n;i++){
            cin>>x[i];
        }
        sort(x,x+n);
        LargestDis();
    }
    return 0;
}