CodeForces 520B Two Buttons

知识点：贪心、递推、反向思考

题目

Vasya has found a strange device. On the front panel of a device there are: a red button, a blue button and a display showing some positive integer. After clicking the red button, device multiplies the displayed number by two. After clicking the blue button, device subtracts one from the number on the display. If at some point the number stops being positive, the device breaks down. The display can show arbitrarily large numbers. Initially, the display shows number n.
Bob wants to get number m on the display. What minimum number of clicks he has to make in order to achieve this result?

输入

The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 104), separated by a space .

输出

Print a single number — the minimum number of times one needs to push the button required to get the number m out of number n.

样例

输入1

4 6

输出1

输入2

10 1

输出2

提示

In the first example you need to push the blue button once, and then push the red button once.
In the second example, doubling the number is unnecessary, so we need to push the blue button nine times.

题意

对一个数，每次选择两个操作：1、乘二 2、减一，最少几次操作可以得到目标数字。

思路

之前做过的题忘了怎么贪了。
因为只有减1能减少数值，且只能减1，无法越过目标数字，所以数字大于目标数字的时候只能使用减1。只有乘2能增加数值，但可以越过目标数字，所以数字小于目标数字的时候，为了使数字大于或等于目标数字，必须乘2，但不是只能乘2，通过减1再乘2也可以达到目的。
通过样例1可以发现：如果选择先乘2再减2，则需要3步；而先减1再乘2，则只需要2步。可证明一个数先乘2再减2相当于这个数先减1再乘2，即2*n-2=(n-1)*2，等式左边使用了3步，而等式右边只用了2步。而且因为数字是任意给的，所以3步可以化成2步，且与数字本身状态无关，表示需要应用贪心思想解题。
通过上述思路可知，若数字小于目标数字，必须乘2，当乘2后的数字与目标数字的距离大于1时，便可以贪心，多次迭代可得到乘2后与目标数字的距离为0或1，因为乘2后得到的数字一定是偶数，则当目标数字为偶数时，迭代后的距离为0，奇数为1。
也就是说能否贪心要看乘2后的状态，根据乘2后的状态推断乘2前需要减1几次。若最开始数字仍然小于乘2之前的数字，根据上述文字，乘2之前必须还有乘2操作。而乘2之前需要减1几次又可通过乘2之前的乘2操作贪心，减1几次可化为减1零次或一次。
循环直到乘2前的数字小于或等于最开始的数字。这个数字又只能由最开始的数字减1几次得到，最开始的数字之前没有任何乘2操作，故减1几次无法化成0次或1次。
实现思路见代码。

代码

//克服WA难，终得AC
#include"bits/stdc++.h"
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define reb(i,a,b) for(ll i=a;i<=b;i++)
#define rev(i,a,b) for(ll i=a-1;i>=b;i--)
#define red(i,a,b) for(ll i=a;i>=b;i--)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

int main() {
   
  ll s,e;//起始数字，目标数字
  cin>>s>>e;
  ll cnt=0;//迭代过程中的操作次数
  while(s<e) {
   //不要写成s<=e，否则当s==e时会继续执行操作，而s之前没有任何操作。
    if(e&1) {
   
    //e为奇数，由乘2后的偶数减1得到，要得到乘2后的偶数需要e加1
      e++;
      cnt++;
    }
    //得到乘2前的数字
    e>>=1;
    cnt++;
  }
  //无法贪心部分为(s-e)次
  cout<<cnt+s-e<<endl;

  return 0;
}