【算法分析】 由于位置的个数很少且要求最小步数，可以考虑从 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 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; 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; }