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

POJ 3258 River Hopscotch (二分)

程序员文章站 2024-03-17 16:04:28
...

http://poj.org/problem?id=3258
题目大意:一条长L的河,有N+2块石头,其中0处和L处各有一块,移走M块石头,求剩下石头间最小距离的最大值。
嗯,最小值最大就应该是二分。从0到L二分距离,这里的判断函数不太好想(主要是我太弱,一开始想跑偏了。。。),判断距离X可不可以的方法是从0处的石头开始每次跳X,若没正好到一块石头,就直接到最近的下一块石头,记录没跳到的石头数num,如果num<=m则返回真。
然后有一个需要注意的点是要先判断一下L可不可以,因为从0到L二分的话最大是L-1。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,L,a[50050],s[50050];
bool vis[50050];
bool check(int p)
{
    int i=0,t=0,j,num=0;
    while(i<=n)
    {
        t=a[i]+p;
        for(j=i;a[j]<t&&j<=n;j++);
        num+=j-i-1;
        i=j;
    }
    return num<=m;
} 
int main()
{
    scanf("%d%d%d",&L,&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    } 
    a[n+1]=L;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        s[i]=a[i]-a[i-1];
    }
    s[n+1]=L-a[n];
    if(check(L))
    {
        printf("%d",L);
        return 0; 
    }
    int l=0,r=L,mid;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(check(mid)) 
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    } 
    mid=(l+r)/2;
    printf("%d",mid);
    return 0;
}