题目描述

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。

农夫有两种移动方式：

从 X 移动到 X−1 或 X+1，每次移动花费一分钟
从 X 移动到 2∗X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

输入格式
共一行，包含两个整数N和K。

输出格式
输出一个整数，表示抓到牛所花费的最少时间。

数据范围
$0≤N,K≤10^5$

样例

输入样例

5 17

输出样例

4

这牛真的好傻

和前两道题一样，用广搜解决。

每个点分出题目给的三种情况，搜到牛为止！

边界问题

首先，搜索到的点必须大于等于0

因为牛不会站到小于0的位置。

如果搜到的点小于零，也只能通过加一回到大于等于0的位置。。。

再拓展一步：从大于等于0的位置走到小于零的位置，也只能通过减一……

所以走到小于0的位置纯属冤枉路！

其次，加一操作和乘二操作不要走k的右边

因为如果到了k的右边，最明智的做法是通过减一走回去。

继续加一或乘二也是冤枉路。。。

最后，所有操作不要走出$10^5$，相信我不说大家也明白

而且如果n的起始位置就大于等于k，也就不用费事了，直接输出n-k

一通优化，最低时间记录直接进了20ms

时间复杂度

这个还真不知道。。。

最坏情况要搜完全数组，复杂度为$O(10^5)$

最好情况也许一次就搜到，也不一定

C++ 代码

#include<iostream>
using namespace std;
const int N=100005;
typedef pair<int,int> PII;
PII q[N];
bool vis[N];
int n,k;

int search(){   //处理步数
    int h=0,t=1;
    q[0]={n,0};     //第一位是遍历到的数，第二位是需要用的步数
    vis[n]=1;

    while(h<t){
        PII now=q[h++];     //取出队头
        if(now.first==k)    //遍历到了牛
            return now.second;

        if(now.first+1<=k&&!vis[now.first+1]){  //满足加一操作的条件
            q[t++]={now.first+1,now.second+1};
            vis[now.first+1]=1;
        }

        if(now.first-1>=0&&!vis[now.first-1]){  //满足减一操作的条件
            q[t++]={now.first-1,now.second+1};
            vis[now.first-1]=1;
        }

        if(now.first<<1<N&&now.first<k&&!vis[now.first<<1]){    //满足乘二操作的条件
            q[t++]={now.first<<1,now.second+1};
            vis[now.first<<1]=1;
        }
    }
}

int main(){
    scanf("%d%d",&n,&k);
    printf("%d",n<k?search():n-k);  //当n>k时只能通过减一一种方式移动
}

原题拓展

我们来让这道题变得略微真实一点，为解决这道题而看的人可以直接退了~

如果题目中的牛没有这么傻，而是不停地背向农夫逃跑

每秒运动一个单位长度，怎么解决？（假设农夫初始位置一定在牛的左侧）

其实不难想象，这时加一和减一的操作都是无法直接抓到牛的

因为这牛生猛的很，全速逃跑之下既然可以保持和农夫一样的速度！

所以农夫抓牛就只能先通过加一、减一、乘二和不动凑到当前的(k+1)/2的位置……

（中途绝不能移动到牛的右侧）

再一个死亡跳跃扑到牛身上。

下面是代码：（这个的数据范围很小，题目的数据范围是支撑不了的）

#include<iostream>
using namespace std;
const int N=100005;
struct qd{
    int n,step,k;
}q[N];
int n,k;
int search(){
    int h=0,t=1;
    q[0]=qd{n,0,k};
    while(h<t){
        qd now=q[h++];
        if(now.n==now.k)
            return now.step;
        if(now.n+1<=now.k)
            q[t++]=qd{now.n+1,now.step+1,now.k+1};  //这里不能用vis，因为牛的位置在不停变动
        if(now.n-1>=0)
            q[t++]=qd{now.n-1,now.step+1,now.k+1};
        if(now.n<<1<=now.k+1)
            q[t++]=qd{now.n<<1,now.step+1,now.k+1};
    }
}
int main(){
    scanf("%d%d",&n,&k);
    printf("%d",search());
}

如果牛足够聪明，每次都能判断农夫下一步想干嘛而进行有效逃避

除非数据对牛太不利，就真的无解了……