我要评论公元9012年，q博士发明了一部太空电梯，与一般电梯不同，太空电梯不能直接到达目点。太空电梯只有上升和下降两个按键，如果电梯上升，
它只能上升当前高度的距离；如果下降，它一次只能下降1米的距离。
为了使大家都能上太空去玩耍，q博士想请你根据电梯的工作原理，计算到达目的点最少需要按几次按键
韶山地图,清漆价格,中国移动广东
20:55:01
公元9012年，q博士发明了一部太空电梯，与一般电梯不同，太空电梯不能直接到达目点。太空电梯只有上升和下降两个按键，如果电梯上升，
它只能上升当前高度的距离；如果下降，它一次只能下降1米的距离。
为了使大家都能上太空去玩耍，q博士想请你根据电梯的工作原理，计算到达目的点最少需要按几次按键
多组输入
每组输入有两个数n和m（1<=n,m<=10^7),表示当前高度n和目的点m
输出计算结果
4 6 10 1
255 999999
2 9
28
题意：电梯有两个按钮 ， 一个是上升目前高度的按钮 ， 另一个是下降1个高度的按钮。
如何从起始高度到达目标高度并要求求出按最少次按钮的次数。
我一开始想的是用dfs，我就去看了下分别在什么情况下使用dfs和bfs。
dfs特点：可以不重不漏的枚举所有可以到达目标状态的路径。（回溯思想 ， 枚举思想）
bfs特点：效率较高，适合于找一条最快到达目标状态的路径。（发散思想）
1 #include <iostream>;
2 #include <stdio.h>;
3 #include <queue>;
4 #include <string.h>;
5 #include <vector>
6 #include <algorithm>
7 #include <math.h>
8 #include <stack>
9 using namespace std;
10 int n , m, vis[1000000] , v[1000000] ;//vis标记查过的点，防止影响结果和效率。 v记录每条路径的目前的按按钮的次数。
11
12 void bfs(int n)
13 {
14 queue<int>q;
15 if(n < m)
16 {
17 q.push(n);
18 vis[n] = 0 ;
19 v[n] = 1 ;
20 if(m % 2 == 1)
21 {
22 m += 1;
23 vis[n] += 1 ;
24 }
25 while(!q.empty())
26 {
27 int a = q.front();
28 q.pop();
29 if(a != 0 && a * 2 <= m &&!v[a * 2]) // 一开始没加 a * 2 < m 该条件 ， 发现数据一大就会爆。
30 {
31 vis[2 * a] = vis[a] + 1 ;
32 v[a * 2] = 1 ;
33 q.push(2 * a);
34 }
35 if(a - 1 >= 0 && !v[a - 1])
36 {
37 vis[a - 1] = vis[a] + 1 ;
38 v[a - 1] = 1 ;
39 q.push(a - 1);
40 }
41 if(a == m)
42 {
43 cout << vis[m] << endl ;
44 break ;
45 }
46 }
47 }
48 else
49 {
50 cout << n - m << endl ;
51 }
52 }
53
54 void init()
55 {
56 memset(v , 0 , sizeof(v));
57 memset(vis , 0 , sizeof(vis));
58 }
59
60
61 int main()
62 {
63 while(cin >> n >> m)
64 {
65 init();
66 bfs(n);
67
68 }
69 return 0 ;
70 }
刷题后感：标记查找过的点是bfs 和 dfs 的重要部分。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论