二分查找水题--疯牛(POJ 2456)

Description

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

* Line 1: One integer: the largest minimum distance

Sample Input

5 3
1
2
8
4
9

Sample Output

3

Hint

OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.

本题表达的是 , 把 C 头牛 放进N 个带编号的牛舍里(隔间),使得任意两个牛之间的距离(位置的最小差值)最大. 比如样本输入,

将3 头牛 放入 1 ,4 ,8 中 , 任意两头牛的距离 是 3 , 4 , 7 . 没有比 3 还要大的最小距离 , 不信, 比如 1 8 9 ,距离 有 7 1 8 ,最小值为1 比3 小 ,.... 不举例了 , 假设任意两个牛之间距离都大于3 , 考虑贪心 ,按隔间大小从小到大排序 ,第一头牛放入 1 号牛舍 ,则至少需要放进 8 号的牛舍 , 此时第三天牛只能进 9号了 , 9-8 =1 >3 ,与假设矛盾

   简化问题, 判断最小距离为X时是否可放下 C头牛 , 那么目标就转化成了,从小到大枚举 X , 判断是否可行 ,直到找到第一个可行的X ,这就是答案 . 为了加快算法速度 ,可使用二分查找代替顺序枚举 ,

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std ;

/* 疯牛问题
    最小距离最大化;
*/
const int MAX =100005 ;
int n , c ;
int L[MAX] ;
bool C(int x )
{
    int i ;
    int temp = L[0] ;
    int count = 1 ;
    for(i = 1 ; i < n ; i++)
    {
        if(L[i]-temp >=x)
        {
            temp = L[i] ;
            count ++ ;
            if(count >= c)
            return true ;
        }

    }
    
    return false ;
}
int Binary_Search()
{
    int left = 0 ;
    int right = L[n-1] - L[0] ;
    while(right >= left )
    {
        int mid = left + (right - left )/ 2 ;
        if(C(mid))
        {
            left = mid + 1 ;
        }
        else
        {
            right = mid - 1 ;
        }   
        
    }
    
    return left -1 ;
    
}
int main()
{
    int i ;
    while (scanf("%d%d",&n,&c)!=EOF)
    {
        for ( i= 0 ; i<n ; i++)
        {
            scanf("%d",&L[i]);
        }   
        sort(L,L+n);
        printf("%d\n",Binary_Search());

    }
    
    
    return 0 ;
}