【算法分析】 由于位置的个数很少且要求最小步数，可以考虑从 nnn 位置开始广搜，同时用一个数组 ddd，did_idi 表示从 nnn 位置到 iii 位置需要的步数，最后输出 dkd_kdk 即可。 【参考代码】 【时间复杂度】 O(1e5)O(1e5)O(1e5) 【预计得分】 100pts100pts100pts

这里有模拟的味道...

有个测试样例错了，所以我特判了 有谁知道为什么错吗

不准抄

#include<iostream> #include<queue> using namespace std; int n,k; queue<int>q; int d[100005]; void bfs(int n,int k){ ~~ while(q.size()){~~ ~~ int f=q.front();~~ q.pop(); if(fk){ cout<<d[f]; break; } if(f-1>=0&&d[f-1]-1){ q.push(f-1); d[f-1]=d[f]+1; } if(f+1<=100000&&d[f+1]-1){ q.push(f+1); d[f+1]=d[f]+1; } if(f2<=100000&&d[f2]-1){ q.push(f2); d[f2]=d[f]+1; } } } int main(){ cin>>n>>k; for(int i=1;i<=100000;i++){ d[i]=-1; } q.push(n); d[n]=0; bfs(n,k); return 0; }

增强KRM262，增强MG42，增强Q33！ 题解：

#include <bits/stdc++.h> using namespace std; int d[100010],n,k; int main() { cin>>n>>k; for(int i =1;i<=100010;i++){ d[i]=-1; } queue<int> q; q.push(n); d[n]=0; while(q.size()){ int r=q.front(); q.pop(); if(r==k){ cout<<d[k]; break; } if(r>=1 && d[r-1] ==-1){ d[r-1]=d[r]+1; q.push(r-1); } if(r<=100010 && d[r+1] ==-1){ d[r+1]=d[r]+1; q.push(r+1); } if(2r<=100010 && d[r2] ==-1){ d[r2]=d[r]+1; q.push(r2); } } return 0; }

#include <bits/stdc++.h> using namespace std; int n,k; int a[100010]; bool vis[100010]; int main(){ cin>>n>>k; queue<int> q; q.push(n); a[n]=0; vis[n]=true; while(q.size()){ int r=q.front(); q.pop(); if(r==k){ cout<<a[k]<<endl; break; } if(r+1<=100000&&vis[r+1]==false){ q.push(r+1); vis[r+1]=true; a[r+1]=a[r]+1; } if(r-1>=0&&vis[r-1]==false){ q.push(r-1); vis[r-1]=true; a[r-1]=a[r]+1; } if(2r<=100000&&vis[2r]==false){ q.push(2r); vis[2r]=true; a[2*r]=a[r]+1; } } }

#include <bits/stdc++.h> using namespace std; const int N = 2e5+5; int n,k; int a[N]; void bfs(int x) { queue<int> q; q.push(x); a[x] = 0; while (!q.empty() ) { int r = q.front() ; q.pop(); if(r == k) { cout<<a[k]; return ; }else { if(a[r-1] == 0 && r>=1){ a[r-1] = a[r]+1; q.push(r-1); }if(a[r+1] == 0 && (r+1)<=100000){ a[r+1] = a[r]+1; q.push(r+1); }if(a[2r] == 0 && (2r)<=100000){ a[r2] = a[r]+1; q.push(r2); } } } } int main() { cin>>n>>k; bfs(n); return 0; }

#include <bits/stdc++.h> using namespace std; struct node{ int x,t; }; queue<node>que; int n,k; bool vis[100010]; int bfs(){ while (!que.empty()){ node a=que.front(); que.pop(); if (a.x==k) return a.t; if (a.x-1>=0 &&a.x-1<=100000 &&vis[a.x-1]==0){ que.push({a.x-1,a.t+1}); vis[a.x-1]=1; } if (a.x+1>=0 &&a.x+1<=100000 &&vis[a.x+1]==0){ que.push({a.x+1,a.t+1}); vis[a.x+1]=1; } if (a.x2>=0 &&a.x2<=100000 &&vis[a.x2]==0){ que.push({a.x2,a.t+1}); vis[a.x*2]=1; } } } int main(){ cin>>n>>k; que.push({n,0}); vis[n]=1; cout<<bfs(); return 0; }