BFS练习_1（C++板块提升计划）【含代码讲解】

zhangjinxuan

题目描述

给你一个数字a，每次可以选择下面四种操作中的一种：

1.把数字a加上一。
2.把数字a乘以2。
3.把数字a乘以3。
4.把数字a减去一。

问把这个a变成b最少需要多少步。

你要回答q个询问，b1,b2,…,bq，输出把a变成b1,b2,…,bq的最小步数。

输入描述

第一行两个整数a,q。

接下来一行q个整数b1,…,bq。

输出描述

输出q个数字，分别表示把a变成b1,b2…,bq的最小步数;

样例输入

3 10
1 2 3 4 5 6 7 8 9 10

样例输出

2 1 0 1 2 1 2 2 1 2

数据规模
对于所有数据，保证1≤a,q,bi≤100000。
测试链接
评论区公布

这道题很有意思，希望大家独立思考完成

现在，上讲解！

讲解
0.1 ： 想一想思路（1)：
一开始，大家的思路应该都是这样的：

写一个函数，每个询问BFS一下就可以了！

但是我们想一想时间复杂度，每一次询问最坏就是O(n), 共q次询问，在这十的五次方这种级别，根本过不了！

这肯定不是正解，大家稍安勿躁，现在介绍第二种方法。

0.2 想一想思路（2):
经过观察，我们发现，一开始的数，他总是固定的，所以，我们可以干什么呢？

我们可不可以在一开始就从一开始的数开始，把所有数都BFS好，然后，每一次询问，不就是O（1)了吗？

这肯定是正解，时间复杂度O(n),一定能过，那我们开始写代码吧！（如果你不明白是什么意思，后面的代码会体会到的）

1. 基本框架：

#include <cstdio> 

using namespace std;

int main() {
        return 0;
}

太煎蛋（简单）了，不说

2.定义变量：

int a, q, x, step[30001], queue[300001], front = 1, rear = 0;

#define MAXN 300001

a代表一开始的数，q代表询问次数，step_i表示从a变到i所要的次数（step必须开3e5+1，后面会体会到的），queue是BFS必须要有的东西，front和rear就是队首队尾。
而MAXN，就是这个数最大变成多少，这个数只要大于300000，不会溢出就可以了。

3.声明BFS函数:

void init();

3.1 ：定义BFS函数，并写出基本的框架：

queue[++rear] = a;
while (rear + 1 != front) {
        ...
}

首先，a肯定要入队，然后在队列非空的情况下将更多的元素入队

3.2：将遍历到的数字加入队列（重点）：

                int front_n = queue[front++];
                int new_n = front_n + 1;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }
                new_n = front_n * 2;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }
                new_n = front_n * 3;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }
                new_n = front_n - 1;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN && new_n >= 0) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }

首先，获取队首元素，然后出队，接着获取新的元素，接着我们首先要判断新元素不等于a的情况并且之前没有遍历过（就是看step_n是不是0，是则遍历过），还要看看是否小于最大值（不然会遍历int范围所有数了，会超时）
注意，最后一个操作要特判，因为可能有<0的情况，这样就溢出了。

倒回去说一遍：step要开3e5+1的原因，因为new_n可能是3e5,如果只开1e5,那么：

step[new_n] == 0 

就溢出了

重点是这里：

step[new_n] = step[front_n] + 1;
queue[++rear] = new_n;

第一步，更新答案step,他要等于 他原本是什么变来的元素 所需的步数 加一（挺长的，尽量理解），然后加入队列

4.main：

scanf("%d%d", &a, &q);
init();
while (q--) {
        scanf("%d", &x);
        printf("%d ", step[x]);
}

输入，再调用刚刚我们写的函数初始化答案，接着执行q次，输入x，输出step_x

5.完整参考代码：

#include <cstdio> 

using namespace std;

int a, q, x, step[300001], queue[300001], front = 1, rear = 0;

#define MAXN 100001

void init() {
        queue[++rear] = a;
        while (rear + 1 != front) {
                int front_n = queue[front++];
                int new_n = front_n + 1;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }
                new_n = front_n * 2;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }
                new_n = front_n * 3;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }
                new_n = front_n - 1;
                if (new_n != a && step[new_n] == 0 && new_n <= MAXN && new_n >= 0) {
                        step[new_n] = step[front_n] + 1;
                        queue[++rear] = new_n;
                }
        }
}
int main() {
        scanf("%d%d", &a, &q);
        init();
        while (q--) {
                scanf("%d", &x);
                printf("%d ", step[x]);
        }
        return 0;
}

总结：这个题还是挺有意思的，方法挺有意思，但是关键是你要想出来

[如果喜欢，别忘了小小的评分，一个荣誉也是爱]

zhangjinxuan

测试链接：http://oj.daimayuan.top/problem/147

zhangjinxuan

@高山 @不二如是
求支持

zhangjinxuan

来个进阶要求：变的过程不能有4（数位不能有4),不能变出来输出-1

高山

支持！！！

zhangjinxuan

高山 发表于 2022-10-2 12:01
支持！！！

感谢支持

zhangjinxuan

怎么这么冷清，求大家支持@元豪