POJ2456 Aggressive cows 二分+判断

题目：http://poj.org/problem?id=2456
大致题意：给出N个数轴上的点的坐标，将C个点插入这N个点中，求C个点之间的距离的最小值的可能的最大值。（有一点绕。。。）
挺简单的题目，就是单纯的二分＋判断
我们利用二分法枚举可能的答案k,则k的最小值为0，最大值为输入数据中坐标位置间的最大距离。
判断可行性的方法：将输入坐标先排序，每次判断k是否可行时，统计所给坐标能否放下(c-1)个距离为k的线段，注意这里是要求放下c-1个而不是c个，因为最后一只牛可以放在最后一个位置，而其后不需要留下距离k.

参考代码：

#include <cstdio>                   //二分+判断
#include <algorithm>
using namespace std;
const int maxn=100000+10;
int pos[maxn];          //存储位置信息
int c,n;                //C头牛，N个位置

bool check(int k)       //检查k是否可行
{
    int cnt=0;
    int last=0,cur=1;
    while(cur<n)
    {
        if(pos[cur]-pos[last]>=k)
        {
            cnt++;
            last=cur++;
        }
        else
            cur++;
    }
    if(cnt<c-1) return false;
    return true;
}

int main()
{
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++)
        scanf("%d",pos+i);
    sort(pos,pos+n);
    int l=0,r=pos[n-1]-pos[0];
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%d",r);
}

最后

以上就是温柔猎豹为你收集整理的POJ2456 Aggressive cows 二分+判断的全部内容，希望文章能够帮你解决POJ2456 Aggressive cows 二分+判断所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。