洛谷 p2678 跳石头 题解

一道裸的二分答案

如果不会分治的去找dalao吧,本蒟蒻只会二分

不知道二分答案的看这里

这位dalao解释的很详细其实只是随便找了一个

那里面貌似也有这个题的题解,但我还是要写(才不是应付老师)

关于二分答案我也稍稍解释一下,

假设你需要50块钱(逃课泡吧)

你:妈妈我要50块钱用来学习

第一种情况(正常情况)

妈妈:给你100块,好好学;

第二种情况

妈妈:给你30块,没那么多了

如果是第一种情况,那么你肯定接受,因为你可以有更长时间泡吧

但是如果是第二种情况呢?

30块并不能满足你的需求,这样的话你一定没等到时候你又得去学校

也就是说,你需要50元,妈妈只能给你50元以上才可以满足要求,但她不能给你太多防止你干坏事

那么这就是重点了,如果你不说你需要50元,妈妈并不知道,但妈妈可以问给你XX元可以吗

那么妈妈就可以找一个范围,她估摸你不会超过要300元泡吧

她就先猜150元,你说可以,那就说明你需要的真正钱数在0到150元之间,也就是说如果妈妈猜出一个钱数(150)可以满足要求;

那么比150多肯定也能满足要求,但149(或更低)不一定

这就是二分答案的适用范围,答案具有单调性(即上一行的解释)

如果知道这个那么再看这个题就简单多啦.

代码奉上

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<stack>

#include<queue>

#include<iostream>

using namespace std;

int n,m,l,aa;

int a[];

bool dd(int x) {

    int kkk=l;//kkk表示还可以移动多少石头

    int c,b=a[];//c代表当前石头,b表示上一个(未搬走)的石头

    for(int i=; i<=m+; i++) {//起点终点都要算上

        c=a[i];

        aa=c-b;

        if(aa>=x) {//符合条件更新上一个点的坐标

            b=c;

        } else {//否则搬走

            if(kkk==)

                return ;

            kkk--;

        }

    }

    return ;

}

void dg(int t,int w) {//二分

    if(t == w||t==w-) {//二分边界

        cout<<t;

        return ;

    }

    int mid = (t+w)/;

    bool bb=dd(mid);

    if(bb == )//如果150块不行

        dg(t,mid);//就从150到300找

    else

        dg(mid,w);//行的话就从0到150找

}

int main() {

//    freopen("stone9.in","r",stdin);

//    freopen("stone.out","w",stdout);

    scanf("%d%d%d",&n,&m,&l);

    int zd=,zx=;

    for(int i=; i<=m; i++) {

        scanf("%d",&a[i]);

        aa=a[i]-a[i-];

        if(aa>zd)//找最大和最小

            zd=aa;

        if(aa<zx)

            zx=aa;

    }

    a[m+] = n;//算上终点

    aa=a[m+]-a[m];

    if(aa>zd)

        zd=aa;

    if(aa<zx)

        zx=aa;

    int i;

    dg(zx,zd);

    return ;

}