AcWing 4300. 两种操作(bfs+贪心)
原题链接
中等
作者:
simoni
,
2022-02-13 14:35:46
,
所有人可见
,
阅读 276
bfs
#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int astep[20010];
int n,m;
int main(){
cin>>n>>m;
memset(astep,-1,sizeof astep);
q.push(n);
astep[n]=0;
while(q.size()){
int t=q.front();
q.pop();
int t1=t*2;
int t2=t-1;
if(t1>0 && t1<20010 &&astep[t1]==-1){
q.push(t1);
astep[t1]=astep[t]+1;
}
if(t1==m){
cout<<astep[t1];
break;
}
if(t2>0 && t2<20010 &&astep[t2]==-1){
q.push(t2);
astep[t2]=astep[t]+1;
}
if(t2==m){
cout<<astep[t2];
break;
}
}
}
贪心
#include<bits/stdc++.h>
using namespace std;
int main(){
long long ans=0;
int n,m;
cin>>n>>m;
while(n!=m){
if(m%2==0&&m>n){
m/=2;
ans++;
}
else {
m++;
ans++;
}
}
cout<<ans;
}
大佬,t1, t2为什么要小于20010呀
数的范围是10000内,乘2操作不会超过20000,为了保险多开10个开到20010
哦哦哦哦哦,谢谢~~
O(∩_∩)O