鱼C论坛

 找回密码
 立即注册
查看: 1886|回复: 6

[技术交流] BFS练习_1(C++板块提升计划)【含代码讲解】

[复制链接]
发表于 2022-10-2 11:45:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 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[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;
}

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

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

评分

参与人数 1贡献 +3 收起 理由
高山 + 3

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-10-2 11:45:35 | 显示全部楼层
测试链接:http://oj.daimayuan.top/problem/147
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-2 11:46:19 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-2 11:50:00 | 显示全部楼层
来个进阶要求:变的过程不能有4(数位不能有4),不能变出来输出-1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-2 12:01:43 | 显示全部楼层
支持!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-10-2 12:08:20 | 显示全部楼层

感谢支持
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-2 13:12:55 | 显示全部楼层
怎么这么冷清,求大家支持@元豪
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-17 00:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表