AcWing算法提高课-2.2.3抓住那头牛

2023-12-31 12:04:50

算法提高课整理

CSDN个人主页:更好的阅读体验


本文同步发表于 CSDN | 洛谷 | AcWing | 个人博客

Start

原题链接
题目描述

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

农夫和牛都位于数轴上,农夫起始位于点 n n n,牛位于点 k k k

农夫有两种移动方式:

  1. x x x 移动到 x ? 1 x-1 x?1 x + 1 x+1 x+1,每次移动花费一分钟
  2. x x x 移动到 2 x 2x 2x,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。

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

输入格式

共一行,包含两个整数 n n n k k k

输出格式

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

数据范围

0 ≤ n , k ≤ 1 0 5 0 \le n,k \le 10^5 0n,k105

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

思路

要求时间最短,考虑 BFS。

分三种情况考虑即可,注意不要越界。

思路较简单,直接上代码。

算法时间复杂度
AC Code

C + + \text{C}++ C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, k;
int q[N], dist[N];

int bfs()
{
    memset(dist, -1, sizeof dist); // -1 表示没走到过
    dist[n] = 0; // 起点距离为 0
    q[0] = n; // 起点入队
    
    int hh = 0, tt = 0;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        if (t == k) return dist[k]; // 如果走到终点, 返回用时
        
        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 (t * 2 < N && dist[t * 2] == -1)
        	dist[t * 2] = dist[t] + 1, q[ ++ tt] = t * 2;
    }
    
    return -1; // 走不到返回 -1
}

int main()
{
    scanf("%d%d", &n, &k);
    printf("%d\n", bfs());
    
    return 0;
}

228aa7bed3e021faf24cf8560d3e47bb.gif

最后,如果觉得对您有帮助的话,点个赞再走吧!

文章来源:https://blog.csdn.net/xingchen_2008/article/details/135313745
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。