A43444. 最少问题输入两个整数n（0<n<100001）和k（0<k<100001），通过对n连续进行加1或减1或乘以2这3种操作，使得n最后结果正好等于k（同一种操作可以使用多次也可以不使用），要求最后输出最少的操作次数。例如：n为5，k为17，通过减1、乘以2、乘以2、加1四次操作得到17，也就是5-1=4，4*2=8、8*2=16，16+1=17.输入描述输入两个整数n和k（n和k之间以一个空格隔开…
填空题
困难
知识点
题目描述
最少问题
输入两个整数n（0<n<100001）和k（0<k<100001），通过对n连续进行加1或减1或乘以2这3种操作，使得n最后结果正好等于k（同一种操作可以使用多次也可以不使用），要求最后输出最少的操作次数。
例如：n为5，k为17，通过减1、乘以2、乘以2、加1四次操作得到17，也就是5-1=4，4*2=8、8*2=16，16+1=17.
输入描述
输入两个整数n和k（n和k之间以一个空格隔开）
输出描述
输出最少的操作次数
样例输入
5 17
样例输出
4
参考答案
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct node {
int pos,step;
};
int v[100005];
queue<node> q;
int main()
{
int n,k;
cin>>n>>k;
v[n]=1;
q.push((node){n,0});
while(!q.empty()){
node t=q.front();
q.pop();
//cout<<t.pos<<" "<<t.step<<endl;
if(t.pos==k){
cout<<t.step<<endl;
break;
}
if(t.pos+1<100005&&v[t.pos+1]==0){
v[t.pos+1]=1;
q.push((node){t.pos+1,t.step+1});
}
if(t.pos-1>=0&&v[t.pos-1]==0){
v[t.pos-1]=1;
q.push((node){t.pos-1,t.step+1});
}
if(t.pos*2<100005&&v[t.pos*2]==0){
v[t.pos*2]=1;
q.push((node){t.pos*2,t.step+1});
}
}
return 0;
}答案解析
评分标准：
20分：能正确输出一组数据；
20分：能正确输出两组数据；
20分：能正确输出三组数据；
上一题
下一题