题目描述

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

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

农夫有两种移动方式：

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

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

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

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

数据范围
0≤N,K≤105

输入样例：
5 17
输出样例：
4

算法1

(朴素bfs) $O(k)$

这题还是挺有意思的，我记得leetcode上有一道和这题类似的可以用贪心来做，这题增加了一个-1操作就导致不能用贪心了，这题的数据范围较小直接bfs就可以了.

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int n,k;

int q[3*N];

int dist[N];

int bfs(int n)
{
    memset(dist,-1,sizeof dist);

    dist[n]=0;

    int tt=0,hh=0;

    q[0]=n;

    while(tt>=hh)
    {
        int t=q[hh++];
        if(t==k)
        {
            return dist[t];
        }
        if(t+1<N&&dist[t+1]==-1)
        {
            dist[t+1]=dist[t]+1;
            q[++tt]=t+1;
        }
        if(t-1>=0&&dist[t-1]==-1)
        {
            dist[t-1]=dist[t]+1;
            q[++tt]=t-1;
        }
        if(2*t<N&&dist[2*t]==-1)
        {
            dist[2*t]=dist[t]+1;
            q[++tt]=2*t;
        }
    }
    return 0;
}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    cin >> n >> k;

    cout << bfs(n) << endl;

    return 0;
}