题目链接

https://codeforces.com/contest/520/problem/B

题目描述

输入两个不同的整数n m，范围都在[1, 1e4]. 每次操作，可以将n*=2，或者n-=1，至少操作多少次可以得到m。

样例

1.iuput

4 6

1.output

2

2.iuput

10 1

2.output

9

算法1

(暴力dp) $O(n^2)$

dp的思想和acwing的这道题有点像，加减乘，不同的是acwing的这道题起点一定是0，但是这道题的起点不一定是0。但是我们发现这道题的时间限制是2s，所以我们可以写一个两重循环，保证大于n和小于n的点都能充分被更新。
这种做法的好处是代码简单，好想，但是缺点就是时间复杂度太大，如果时间缩短成了一秒，就会TLE。

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

const int N = 1e4+10;

int n, m;
int w[N];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin>>n>>m;
    memset(w, 0x3f, sizeof w);
    w[n] = 0;

    for(int j=0;j<N;j++)
    {
        for(int i=1;i<N;i++)
        {
            if(i*2<N) w[i*2]=min(w[i]+1, w[i*2]);
            if(i<N-1) w[i]=min(w[i], w[i+1]+1);
        }
    }
    cout<<w[m]<<endl;

    return 0;
}

算法2

(找规律) $O(log(n))$

我们发现，如果m<=n时，最优方法是n只能通过减一来变到m，不能有乘以2的操作，一旦乘以了2，操作数量一定会变大。
那么当m>n时，我们可以反过来考虑，如何从m变到n，那么操作就变成了每次除以2（当前数是偶数的情况下），或者加上1。我们只需要在m>n的情况下，如果m为奇数，就先加1，再除以2；如果m为偶数，就直接除以2，直到m<=n。再让m不停地加1直到与n相等即可。下证为什么一直让m除以2，尽量不要加1，除非当前m为奇数。
假设m为偶数（奇数也是一样的证明），每次让m加上2再除以2，和直接让m除以2再加1的结果是一样的，但是前者的操作次数是3，后者的操作次数是2，说明操作2优于操作1。
假设m在区间($2^k*n$, $2^{k+1}*n$]内，可以把m拆分为$2^k*n+z$。这样拆分区间的原因是每次m除以2，都一定会跳掉上一个区间。如果z等于0，那么我们只要不停地除以2就好了，最后会直接等于n；如果z不为0，我们每次在除以2之前一定不会一直加，把m加到超出$2^{k+1}*n$，因为超出后m除以2还是在这个区间，但是我们需要让m跳掉上一个区间。我们可以发现z的取值范围一直小于当前区间的长度，假设按上述算法最后m变成了n-y,那么我们最后只需额外在加上y个1就好了，除去必须加1和除2的操作外操作数为y。若我们在整个过程中加了x个1（除去因为m是奇数必须加一的数量），x一定为偶数（不然不能整除2），那么m最后变成了n-y+x/2,最后还需加上（y-x/2）个1，但是中途还需要x次操作加1，所以除去必须加1和除2的操作外还要y+x/2此操作，这比不额外加1的操作数多。证毕。

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;

    int res = 0;
    if(m<=n) res = n - m;
    else{
        while(m>n){
            if(m % 2) m++, res++; // 如果m是奇数
            m /= 2, res++; // 将m整除2
        }

        while(m<n) res++, m++;   
    }

    cout<<res<<endl;

    return 0;
}

算法3

(二进制) $O(1)$

如果m<=n，我们还是直接得出答案即可。当m>n时，m的二进制位数一定大于n我们可以将n的位数将m分为两个部分，前部分拿到m的开头长度与n一样的二进制数start，后部分拿到m剩余的数end，我们还是可以这样考虑：每次将m除以2或者加1。end就是每次除以2消去的，在二进制下就是每次将数字向右移一位，结果会先加上n-start，这个是每次加1的次数，再加上end的长度，这个是每次除以2的次数，如果end不为0的话，我们在遇到end的结尾为1时，需要先加上1在除以2，所以在加上加1的次数，并且start++，因为不停地加1，最终一定会加到start里。如果发现start是大于n的话，表示这种情况是不成立的，需要将start的位数减1，再重复计算一遍即可，这时是一定成立的，因为n比start多了一位，即使start+1，也不会超过n。
那为什么不直接计算第二种情况，反正它始终成立，而是要先看一下第一种情况呢？这时因为在第二种情况下，end不仅要多移一位，start也会更小于n，变化的次数会更多，所以先考虑第一种情况。

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

const int N = 1e7+10;

int n, m;
int x, y;
LL f[N];

int get_0_b(int x)  // 返回32位下x的前导0  比如101001 返回16
{
    int res = 0;
    for(int i=31;~i;i--){
        if((x>>i&1)==0) res++;
        else break;
    }
    return res;
}

int get_1(int x)  // 返回x的二进制中有多少位数是1，比如01011 返回3
{
    int res = 0;
    for(int i=0;i<32;i++) res += x>>i&1;
    return res;
}

int get_0_e(int x)  // 返回x有多少的后缀零 比如1001001000 返回3, 1001010 返回1
{
    int res = 0;
    for(int i=0;i<32;i++){
        if((x>>i&1)==0) res++;
        else break;
    }
    return res;
}

void solve()
{
   cin>>n>>m;
   if(m<=n){
       cout<<n-m<<endl;
       return;
   }
   int a = 32 - get_0_b(n), b = 32 - get_0_b(m);
   if(b>a){
       int deta = b - a;
       int start = m >> deta;
       int end = m & ((1<<deta) - 1);
       int res = n - start + deta;
       if(end){
           start++;
           res += deta - get_1(end) - get_0_e(end);
       }
       if(start <= n){
           cout<<res<<endl;
           return;
       }
   }

   int deta = b - a + 1;
   int start = m >> deta;
   int end = m & ((1<<deta) - 1);
   int res = n - start + deta;
   if(end) res += deta - get_1(end) - get_0_e(end);
   cout<<res<<endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    solve();

    return 0;
}