BFS练习_1（C++板块提升计划）【含代码讲解】
本帖最后由 zhangjinxuan 于 2022-10-2 11:45 编辑题目描述
给你一个数字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, queue, 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;
int new_n = front_n + 1;
if (new_n != a && step == 0 && new_n <= MAXN) {
step = step + 1;
queue[++rear] = new_n;
}
new_n = front_n * 2;
if (new_n != a && step == 0 && new_n <= MAXN) {
step = step + 1;
queue[++rear] = new_n;
}
new_n = front_n * 3;
if (new_n != a && step == 0 && new_n <= MAXN) {
step = step + 1;
queue[++rear] = new_n;
}
new_n = front_n - 1;
if (new_n != a && step == 0 && new_n <= MAXN && new_n >= 0) {
step = step + 1;
queue[++rear] = new_n;
}
首先，获取队首元素，然后出队，接着获取新的元素，接着我们首先要判断新元素不等于a的情况并且之前没有遍历过（就是看step_n是不是0，是则遍历过），还要看看是否小于最大值（不然会遍历int范围所有数了，会超时）
注意，最后一个操作要特判，因为可能有<0的情况，这样就溢出了。
倒回去说一遍：step要开3e5+1的原因，因为new_n可能是3e5,如果只开1e5,那么：
step == 0
就溢出了
重点是这里：
step = step + 1;
queue[++rear] = new_n;
第一步，更新答案step,他要等于 他原本是什么变来的元素 所需的步数 加一（挺长的，尽量理解），然后加入队列
4.main：
scanf("%d%d", &a, &q);
init();
while (q--) {
scanf("%d", &x);
printf("%d ", step);
}
输入，再调用刚刚我们写的函数初始化答案，接着执行q次，输入x，输出step_x
5.完整参考代码：
#include <cstdio>
using namespace std;
int a, q, x, step, queue, front = 1, rear = 0;
#define MAXN 100001
void init() {
queue[++rear] = a;
while (rear + 1 != front) {
int front_n = queue;
int new_n = front_n + 1;
if (new_n != a && step == 0 && new_n <= MAXN) {
step = step + 1;
queue[++rear] = new_n;
}
new_n = front_n * 2;
if (new_n != a && step == 0 && new_n <= MAXN) {
step = step + 1;
queue[++rear] = new_n;
}
new_n = front_n * 3;
if (new_n != a && step == 0 && new_n <= MAXN) {
step = step + 1;
queue[++rear] = new_n;
}
new_n = front_n - 1;
if (new_n != a && step == 0 && new_n <= MAXN && new_n >= 0) {
step = step + 1;
queue[++rear] = new_n;
}
}
}
int main() {
scanf("%d%d", &a, &q);
init();
while (q--) {
scanf("%d", &x);
printf("%d ", step);
}
return 0;
}
总结：这个题还是挺有意思的，方法挺有意思，但是关键是你要想出来
[如果喜欢，别忘了小小的评分，一个荣誉也是爱] 测试链接：http://oj.daimayuan.top/problem/147 @高山 @不二如是
求支持{:10_254:} 来个进阶要求：变的过程不能有4（数位不能有4),不能变出来输出-1 支持！！！ 高山 发表于 2022-10-2 12:01
支持！！！
感谢支持 怎么这么冷清，求大家支持{:10_256:}@元豪
页:
[1]