时间限制:1秒
空间限制:262144K
给定两个-100到100的整数x和y,对x只能进行加1,减1,乘2操作,问最少对x进行几次操作能得到y?
例如:
a=3,b=11: 可以通过3*2*2-1,3次操作得到11;
a=5,b=8:可以通过(5-1)*2,2次操作得到8;
a=3,b=11: 可以通过3*2*2-1,3次操作得到11;
a=5,b=8:可以通过(5-1)*2,2次操作得到8;
输入描述:
输入以英文逗号分隔的两个数字,数字均在32位整数范围内。
输出描述:
输出一个数字
输入例子1:
3,11
输出例子1:
3
思路:广度优先搜索。(队列实现)
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std; int main() {
int x, y;
int cnt = ;
bool flag = false;
scanf("%d,%d", &x, &y);
queue<int> q;
q.push(x);
while (!q.empty()) {
int len = q.size();
for (int i = ; i < len; i++) {
int tmp = q.front();
q.pop();
if (tmp == y) {
flag = true;
break;
} else {
q.push(tmp + );
q.push(tmp - );
q.push(tmp * );
}
}
if (flag)
break;
cnt++;
}
cout << cnt << endl;
return ;
}
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std; int main() {
int x, y;
scanf("%d,%d", &x, &y);
queue<pair<int, int> > q;
pair<int, int> tmp({x, });
q.push(tmp); while (!q.empty()) {
tmp = q.front();
q.pop();
if (tmp.first == y) {
cout << tmp.second << endl;
break;
} else {
q.push({tmp.first + , tmp.second + });
q.push({tmp.first - , tmp.second + });
q.push({tmp.first * , tmp.second + });
}
}
return ;
}