马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
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
样例输出数据规模
对于所有数据,保证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函数:
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] = 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;
}
总结:这个题还是挺有意思的,方法挺有意思,但是关键是你要想出来
[如果喜欢,别忘了小小的评分,一个荣誉也是爱] |