[ACM] poj 2456 Aggressive cows （二分查找） - 同学少年 - 博客园

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

先按贪心，第一头牛肯定被放在第一个牛舍里，排序 1 2 4 8 9

第二头牛可以放在2，也可以放在4，假设第二头牛放在2 ，与第一头牛的距离为1 ，假设第三头放在9，与第二头的距离为7，那么，最近的两头牛之间的最大距离为1

最有解为 第一头牛放在1  第二头牛放在4 ，第三头牛放在9 ，那么 4-1=3  9-4=5 ，最近的两头牛之间的最大距离为3

也就是求相邻两头牛之间距离的最小值（取最大）。这个距离采用二分的形式进行判断。

Code from http://www.tuicool.com/articles/fAbyYf

int judge(int x)
{
  int cot=1;
  int tmp=a[0];
  for(i=1;i<n;i++)
  {
    if(a[i]-tmp>=x)//距离大于栏的间隙 可以放下
    {
      cot++;
      tmp=a[i];
      if(cot>=c)//可以排下c头牛
        return true;
    }
  }
  return false;
}
int slove()//二分查找
{
  int l=0;//最小距离
  int r=a[n-1]-a[0];//最大距离
  while(l<=r)
  {
    int mid=(l+r)/2;
    if(judge(mid))//可以排下c头牛 
      l=mid+1;
    else
      r=mid-1;
  }
  return l-1;
}

Also check http://www.tuicool.com/articles/qQnMRf

int ok(int k) {
  int last = 0;
  int cur;
  for(int i=1; i<c; ++i) {
    cur = last + 1;
    while(cur<n && x[cur] - x[last] < k)
      cur++;
    if(cur==n) return false;
    last = cur;
  }
  return true;
}
int main() {
  scanf("%d%d",&n, &c);
  for(int i=0; i<n; ++i) scanf("%d", &x[i]);
  sort(x, x+n);

  int l = 0, r = (x[n-1] - x[0])/(c-1);
  for(int i=0; i<100; ++i) {
    int mid = (l+r)/ 2;
    if( !ok(mid) )  r = mid;
    else l = mid;
  }
  printf("%d\n", l);
  return 0;
}

Read full article from [ACM] poj 2456 Aggressive cows （二分查找） - 同学少年 - 博客园