思路(二进制)
(第一次写题解,请谅解。。。)
以下使用二进制来理解…
首先观察到,如果我进行一次操作2(即减1),之后一直使用$k$次操作1(即乘2),那么相比于$k+1$次乘2操作来说,最终得出来的数在二进制表示时第 $k + 1$ 位会少1(如果没看懂,那就写一个二进制自己演示一遍吧)。
基于上面的结论,回到题目,我们让$n$一直乘2,只到他比$m$大时,获得他们的差$a$,我们把$a$理解为多出来的部分,并且将 $a$化成二进制展开(不断除以2),看到这里你应该已经理解了,$a$的二进制中有1的部分为多余的部分,说明我们可以在某次乘2操作前进行减1(也就是操作数+1),这样这个1就没有了…
但是$!!!$
如果仅仅是这样,那就大错特错了。
考虑以下样例
99 100
你会发现我们只进行了一次乘2操作,也就是说,我们只能消除第2位的1,后面的都不能进行消除。也就是说,我们就要停止数1(除以2)的操作了。怎么办呢,其实很简单,我们只需要在最开始操作前,把这些多出来的数减1就好了,而这多出来的数,不就是我们停止数1(停止除以2)后剩下的$a$吗,最后答案加上剩下的$a$就行了。
求个赞,拜托了
C++ 代码
#include<cstdio>
#include<algorithm>
using namespace std ;
int main(void ){
int n , m ;
scanf("%d%d" , &n ,&m);
int ans = 0 ;
while(n < m){
ans++;
n *= 2 ;
}
int cnt = ans ; //cnt 表示我们最多进行cnt 次乘2操作
int a = n - m ; //a 为多出来的数
while(a && cnt--){
if(a & 1)ans++; //检查二进制中1的个数,如果a的二进制位数多于cnt,那么到第cnt + 1 位要退出要退出
a >>= 1 ;
}
ans += a ; //如果a不为0,说明我们要在乘2之前剪掉这些数
printf("%d" , ans);
return 0 ;
}