欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2456 Aggressive cows 二分

程序员文章站 2024-03-16 09:01:04
...

题目大意:

给你n个牛舍,把c只牛放在牛舍里,要求最近的两头牛之间距离最大。

思路:

直接二分,从最大长度开始二分查找,选取一个长度,然后选择两个牛圈大于等于这个长度进行安置牛,最后判断能不能把所有的牛放进去,如果可以left=mid找更大的,如果不行,说明太大了,right=mid找小一点的

    #include<cstdio>  
    #include<cstring>  
    #include<algorithm>  
    using namespace std;  
    const int MAXN= 100000+10;  
    int a[MAXN],n,c;  
    bool ok(int dis)  
    {  
        int last=0;  
        for(int i=1;i<c;i++)  
        {  
            int next=last+1;  
            while(next < n && a[next]-a[last] < dis) next++;  //找大于等于所选的长度的马厩
            if(next>=n)  
                return false;  //放不下所有的牛
            last=next;  
        }  
        return true;  
    }  
    int main()  
    {  
        while(~scanf("%d%d",&n,&c))  
        {  
            for(int i=0;i<n;i++)  
                scanf("%d",&a[i]);  
      
            sort(a,a+n);  
            int L=0,R=a[n-1]+1;  //为什么加1,因为这种方法是一个左闭右开区间[   )所以如果不加1答案又恰好是最右边的值,则取不到
           while(L<R-1)  
            {  
                int mid=L+((R-L)>>1);  
                if(ok(mid))  
                    L=mid;  
                else  
                    R=mid;  
            }  
            printf("%d\n",L);  
        }  
        return 0;  
    }