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

「poj」 2456 Aggressive cows(二分)

程序员文章站 2024-03-16 08:56:40
...

题目链接:http://poj.org/problem?id=2456

题意:给出n个点,求其中m个点之间的最大的最小距离。

最大化最小值用二分比较多,这道题初始时 l 就是0, r 就是 a[n]a[1] ,然后二分查找最大值。

AC代码:

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 1e5+100;
const int INF = 0x3f3f3f3f;
int n,m;
int a[maxn];
bool solve(int x){
    int pos = 1,cnt = 1;    //贪心思想第一只牛一定是在a[1]这个点,所以pos初始为1。
    for(int i=2;i<=n;++i){
        if(a[i] - a[pos] >= x){    //满足条件,更新pos
            cnt++;
            pos = i;
        }
    }
    if(cnt >= m)    return true;    //可以放下m头牛
    return false;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)   scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int l = 0,r = a[n] - a[1],mid;
    while(l<=r){    //注意有等号
        mid = (l+r)/2;
        if(solve(mid)){     //[l,r]可以,试试[mid+1,r]行不行,找最大值
            l = mid+1;
        }
        else    r = mid-1;    //缩小范围
    }
    printf("%d\n", l-1);    /*这个可能太好理解,我自己是这么想得。
    如果l==r时,solve(mid)为真那么l会加一,所以需要减一。
    如果l==r时,solve(mid)为假,而又有l==mid,所以此时的l不合题意,应该是上一个状态的l合题,即l-1.*/
}