我真的不想水题解，你们说我水过吗
认为没水过的点个赞，认为水过的给自己两个大嘴巴子。
先上题目
小信有两个数 x 与 y。
小信可以对 x 进行 3 种 操作：
1.让 x 等于 x+1
2.让 x 等于 x−1
3.让 x 等于 2⋅x
小信想知道把 x 变成 y 至少需要操作多少次。
输入格式：
第一行包含一个整数 T，表示 T 组测试数据。
对于每一组测试数据：
第一行包含两个整数 x, y。
输出格式：
对于每一组测试数据，输出一个整数表示答案。
样例1输入：
1
5 17
样例1输出：
4
约定与提示：
对于100%的数据，1≤t≤10, 1≤x,y≤105
梳理一下
现在规划一下思路
1.因为数据较大，用bfs比较好。
2.因为这里有大量的×2，所以开大一点数组不是错
先写输入
cin>>T;
while(T--){
cin>>x>>y;
bfs();
}
这里加一个特判
如果x>y那么cout<<x-y<<endl;continue;
因为他没有÷2的选项，所以只能一个个减下去。
//现在开头变成了这样
int main()
{
cin>>T;
while(T--){
cin>>x>>y;
if(x>y){
cout<<x-y<<endl;
continue;
}
bfs();
}
return 0;
}
//还要加memset
int main()
{
cin>>T;
while(T--){
cin>>x>>y;
memset(vis,0,sizeof(vis));
if(x>y){
cout<<x-y<<endl;
continue;
}
bfs();
}
return 0;
}
然后开头好了
开始写bfs；
先写最基础的
void bfs(){
queue<pair<long long,int> > q;//这里的pair<long long,int>是一个和结构体很像的东东，为数不多不一样的是只能放两个
q.push({x,0});
vis[x]=1;
while(!q.empty()){
long long tx=q.front().first;
int ty=q.front().second;
q.pop();
if(tx==y){
cout<<ty<<endl;
return;
}
}
}
接下来好写了
加上推入
q.push({tx+1,ty+1});
q.push({tx-1,ty+1});
q.push({tx*2,ty+1});
和防止重复的vis
if(!vis[tx+1]){
q.push({tx+1,ty+1});
vis[tx+1]=true;
}
if(!vis[tx-1]){
q.push({tx-1,ty+1});
vis[tx-1]=true;
}
if(!vis[tx*2]){
q.push({tx*2,ty+1});//cout<<" "<<tx*2<<" ";
vis[tx*2]=true;//这里一定要开大点不然就爆了
}
最后剪枝让他不会过大，过小
if(tx+1<y*2)
if(!vis[tx+1]){
q.push({tx+1,ty+1});
vis[tx+1]=true;
}
if(tx-1>1)
if(!vis[tx-1]){
q.push({tx-1,ty+1});
vis[tx-1]=true;
}
if(tx*2<y*3)
if(!vis[tx*2]){
q.push({tx*2,ty+1});//cout<<" "<<tx*2<<" ";
vis[tx*2]=true;
}
最后的AC代码
#include <bits/stdc++.h>
using namespace std;
const long maxn=2000000+5;
int x,y,T;bool vis[maxn];
void bfs(){
queue<pair<long long,int> > q;
q.push({x,0});
vis[x]=1;
while(!q.empty()){
long long tx=q.front().first;
int ty=q.front().second;
q.pop();
if(tx==y){
cout<<ty<<endl;
return;
}
if(tx+1<y*2)
if(!vis[tx+1]){
q.push({tx+1,ty+1});
vis[tx+1]=true;
}
if(tx-1>1)
if(!vis[tx-1]){
q.push({tx-1,ty+1});
vis[tx-1]=true;
}
if(tx*2<y*3)
if(!vis[tx*2]){
q.push({tx*2,ty+1});
vis[tx*2]=true;
}
}}
int main()
{
cin>>T;
while(T--){
cin>>x>>y;
memset(vis,0,sizeof(vis));
if(x>y){
cout<<x-y<<endl;
continue;
}
bfs();
}
return 0;
}