题目内容

P2678 跳石头

解题思路

跳石头这道题显然满足单调性和有界性,可以用二分答案求解

枚举题目要求的最短跳跃距离,思考:最短跳跃距离越大,需要挪走的石头越多,这显然满足单调性,又由于能挪走的石头有一个上限M,因此可以使用二分答案进行求解。

求解时从区间[1,L]开始二分,取中点mid,然后开始模拟跳石头,如果下一个石头离上一个石头的距离小于了取的mid,则说明这块石头应该被挪走,计数器cnt加一

如果中途时cnt大于了M,说明需要挪走的石头数量超过了上限,即mid取的过大,方案不可行,接下来就继续二分[1,mid-1],一步步缩小二分的范围。

同理,如果结束时cnt\leq M,说明该方案可行,但是可能不是最优解,mid还可以取更大,因此继续二分[mid,L],依次求解。

到最后如果到了区间[l,r]l=r,说明已经找到了最优解,输出即可。

#include <cstdio>

int L,n,m,d[50005];//见题意

bool judge(int x)
{
    int cnt=0;//表示需要挪多少块石头
    int now=0,i=0;//now表示当前人在的石头标号,i表示当前处理的石头标号
    while(i<n+1)//注意是n+1
    {
        ++i;
        if(d[i]-d[now]<x)//如果两块石头中间的距离小于需要查找的mid值
            cnt++;
        else
            now=i;
    }
    return cnt<=m;//返回判断结果
}

int binary()//二分答案
{
    int l=1,r=L;//表示二分边界
    int ans;//当前答案
    while(l<=r)//当l<=r的时候
    {
        int mid=l+r>>1;//用位运算更快???
        if(judge(mid))//如果这个满足条件
            ans=mid,l=mid+1;//那么把它存下来,更新二分边界
        else//如果不满足条件的话
            r=mid-1;//mid取太大了,更新二分边界
    }
    return ans;//返回答案
}

int main()
{
    scanf("%d %d %d",&L,&n,&m);
    d[0]=0;
    for(int i=1;i<=n;i++) scanf("%d",d+i);
    d[n+1]=L;
    printf("%d\n",binary());
    return 0;
}

反思

二分答案,当题目中有最大的最小或者最小的最大时一般就可以使用,需要条件满足单调性和有界性。

比如这个跳石头,跳的最短距离越大需要挪走的石头越多,就可以使用二分答案枚举答案求解

然鹅我还是不会二分答案

最后修改日期: 2020年1月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。