解题报告 P2678 跳石头

题目内容

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;
}

反思

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

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

然鹅我还是不会二分答案