hello大家好，欢迎大家访问 林深时不见鹿 的博客，算法小白，记录学习的点滴日常，致力于通俗易懂的题解，相遇即是上上签，如有不足，还请多多指教。
目录
1.题目2.思路(1) 逆向思维3.代码4思路(2) bfs5.代码
1.题目
给定一个自然数，有两种操作， 1.将数字乘 2。 2.将数字减去 1。 如果某次操作后数字不为正数，则终止。 一开始你拥有的是数字 n 。
你的目标是得到数字 m 。为了获得这个结果，他最少需要做多少次操作？
输入格式 输入一行，两个整数 n 和 m (1 ≤ n, m ≤ 104)，以空格分隔。
输出格式 输出最少操作的次数。
输入输出样例 输入 2 3 输出 2 输入 11 1 输出 10 样例说明 样例1中，先乘2，再减1
样例2中，疯狂减一即可
2.思路(1) 逆向思维
1.如果n>m，只能通过减一操作来获得m。 2.n<=m，考虑逆向思维，n变到m需要n-1和n*2两种操作，那么反过来由m变到n需要m+1和m/2两种操作，对应的操作数是相同的，但逆向更有助于我们思考。 3.如果m是奇数，无法进行m/2操作，进行m+1，使其变为偶数。如果m是偶数，直接m/2，重复上述操作，直到n>=m时退出，最后的操作数再加上n-m。
3.代码
#include<iostream>
#include<cmath>
using namespace std
;
int main()
{
int n
,m
;
cin
>>n
>>m
;
int ans
=0;
if(n
>m
)
{
ans
=n
-m
;
}
else
{
while(n
<m
)
{
if(m
%2==0)
{
m
/=2;
ans
++;
}
else
{
m
++;
ans
++;
}
}
ans
+=n
-m
;
}
cout
<<ans
<<endl
;
return 0;
}
4思路(2) bfs
这道题非常类似于 AcWing 1100. 抓住那头牛可以说是那道题的缩小版 直接bfs搜索。
5.代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std
;
const int N
=1e4+10;
int q
[N
];
int dist
[N
];
int n
,m
;
int bfs()
{
memset(dist
,-1,sizeof(dist
));
int hh
=0,tt
=0;
q
[0]=n
;
dist
[n
]=0;
while(hh
<=tt
)
{
int t
=q
[hh
++];
if(t
==m
) return dist
[m
];
if(t
-1<N
&&dist
[t
-1]==-1)
{
dist
[t
-1]=dist
[t
]+1;
q
[++tt
]=t
-1;
}
if(t
*2<N
&&dist
[t
*2]==-1)
{
dist
[t
*2]=dist
[t
]+1;
q
[++tt
]=t
*2;
}
}
return -1;
}
int main()
{
cin
>>n
>>m
;
cout
<<bfs()<<endl
;
return 0;
}
