poj 2456 Aggressive cows(二分搜索)题解

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 Outpu

3

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[100005];
    int n,m;
    while(~scanf("%d %d",&n, &m))//cin>>n>>m)
    {
        for(int i=0;i<n;++i)
          scanf("%d",&a[i]);//scanf("%d",&a[i]);
        sort(a,a+n);
        int low=0,high=a[n-1];

        int min_Mdistation=0;//最小的最大距离值
        while(low<=high)
        {
           int ans=1,postation=a[0];//第ans头奶牛放于postation位置。
           int distance_mid=(high+low)/2;//先假定那个最小距离d为多少呢，嗯，就是distance_mid
           for(int i=1;i<n;++i)//在最小的最大距离（distance_mid下)寻找m个奶牛的要放置的位置，（用ans来标记个数，最终只记录个数，不记录所放置的位置）
           {
               if(a[i]-postation>=distance_mid)
               {
                   postation=a[i];
                   ans++;
                   //在这儿说明滴ans头奶牛的位置：postation
               }
           }
           if(ans>=m)//haha,说明在此时的最小的最大距离下找到了满足m头牛的位置，
           {
               min_Mdistation=max(min_Mdistation,distance_mid);//那么就记录下这个距离值吧
               low=distance_mid+1;//在次更新下一次的左始点，（下一次low>high的时候，那最小的最大距离自然就是min_Mdistation喽。)
           }
           else//ai,没有找到满足让m头牛都放置下的地方哦，那就在下次二分的时候减小一下最小的最大距离值吧。
            high=distance_mid-1;
        }
        cout<<min_Mdistation<<endl;
    }
    return 0;
}