POJ-2456疯牛（二分搜索+最小值最大化）

最新推荐文章于 2022-01-19 12:10:49 发布

donCoder

最新推荐文章于 2022-01-19 12:10:49 发布

阅读量493

点赞数

分类专栏：蓝桥杯 ACM

本文链接：https://blog.csdn.net/doncoder/article/details/79965925

版权

蓝桥杯同时被 2 个专栏收录

28 篇文章

订阅专栏

ACM

21 篇文章

订阅专栏

描述农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000).
但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？

输入

有多组测试数据，以EOF结束。
第一行：空格分隔的两个整数N和C
第二行——第N+1行：分别指出了xi的位置

输出

每组测试数据输出一个整数，满足题意的最大的最小值，注意换行。

样例输入

样例输出

题意要表达的是：把C头牛放到N个带有编号的隔间里，使得任意两头牛所在的隔间编号的最小差值最大。例如样例排完序后变成1 2 4 8 9，那么1位置放一头牛，4位置放一头牛，它们的差值为3；最后一头牛放在8或9位置都可以，和4位置的差值分别为4、5，和1位置的差值分别为7和8，不比3小，所以最大的最小值为3。

分析：这是一个最小值最大化的问题。先对隔间编号从小到大排序，则最大距离不会超过两端的两头牛之间的差值，最小值为0。所以我们可以通过二分枚举最小值来求。假设当前的最小值为x，如果判断出最小差值为x时可以放下C头牛，就先让x变大再判断；如果放不下，说明当前的x太大了，就先让x变小然后再进行判断。直到求出一个最大的x就是最终的答案。

#include <iostream>
#include <algorithm>
using namespace std;
int n,c;
int x[1000000002];
bool binary_search(int a){
    int temp=x[0];
    int cnt=1;
    for(int i=0;i<n;i++){
        if(x[i]-temp>=a){
            temp=x[i];
            cnt++;
            if(cnt>=c)
                return true;
        }
    }
    return false;
}
int main(){
    cin>>n>>c;
    for(int i=0;i<n;i++)
        cin>>x[i];
    sort(x,x+n);
    int lb=1,rb=x[n-1]-x[0];
    int mid=0;
    while(lb<=rb){
        mid=(lb+rb)/2;
        if(binary_search(mid))
            lb=mid+1;
        else
            rb=mid-1;
    }
    cout<<mid;
    return 0;
}