2346: 信息学奥赛一本通T1433-愤怒的牛（二分查找）

解题思路:

先理解题目，会给出隔间的编号和有几头牛，将牛尽可能分远的住进隔间，使任意两头牛之间的最小距离尽可能的大，问这个最小距离最大是多大

以给出的数据为例：

5 3
1 2 8 4 9

这五个隔间可以任意选三个住牛，可以是1 2 4，1 2 8 但是这样有的牛就会挨的太近了，还有更远的分法：1 4 9

所以答案输出牛之间的最小距离（4-1）=3

我们先将房间号进行排序，然后得出可能的最大距离为（max-min+1）/牛的数量

从最大的距离到1开始遍历，查看每头牛都在这个距离下是不是能全住进房间，能就输出这个距离，结束遍历，不能就继续遍历

这样做最坏的情况下的时间复杂度是n^2，数据规模是1,000,000,000，可能会时间超限

所以这里在查找距离的时候使用二分查找，时间复杂度是nlogn，

当然，在对房间号进行排序的时候也不能使用简单的冒泡排序等，那样时间复杂度也会变成n^2

这是使用c语言自带的排序，它在头文件stdlib.h里，是使用快速排序进行实现的，时间复杂度是nlogn

参考代码:

#include <stdio.h>
#include <stdlib.h>
  
int gg(const void *x,const void *y){
    return *(int *)x-*(int *)y;//从小到大排序
}
  
int n,m,p[100001]={0};//全局变量不用传递，m是牛的数量
  
int check(int z){
    int i;
    int count=1;//第一个牛舍放牛
    int k=p[0]+z;
    for(i=1;i<n;i++){
        if(p[i]>=k){//后面的牛舍要满足大于等于k才能放牛
            count++;
            k=p[i]+z;
        }
    }
    if(count>=m){//可以放的位置超过牛的数量
        return 1;
    }else{
        return 0;
    }
}
  
int main ()
{
    int i;
    int x=0,y=0,z=0;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%d",&p[i]);
    }
    qsort(p,n,sizeof(p[0]),gg);//排序
      
    x=1;
    y=(p[n-1]-p[0]+1)/m;
    z=(x+y)/2;
    while(x<=z){//二分查找
        if(check(z)==0){//如果返回值是0说明z的值较大，要向小的一方查找
            y=z-1;
        }else{
            x=z+1;
        }
        z=(x+y)/2;
    }
    printf("%d",z);
      
    return 0;
}