2595 X之于Y 思维

阅读量：4319 次

发布时间：2019-06-06

本文共 1133 字，大约阅读时间需要 3 分钟。

小Y上课无聊摸鱼，他在纸上随意写下了两个数字X和Y。现在他想把X通过某种方法变成Y，为了把让这个过程更加有趣，所以他限定自己只能使用两种操作：

1、把当前X乘二

2、把当前X减一

因为课堂上的时间有限，所以他用了最少的操作次数实现这一过程。下课后，路过的qz看到了小Y纸上写着的X和Y，他一秒钟以内就知道了小Y用了多少次操作。那么问题来了，小Y到底用了多少次操作呢？

收起

输入

两个数字表示X和Y其中1<= X <= 1,000,000,0001<= Y <= 1,000,000,000

输出

一个数字，表示把X变成Y最少需要多少次操作

输入样例

1 1000000000

输出样例

39 考虑由y变成x，那么只有2种操作：1.y/=2 2.y+=1 ； 当y为奇数，那么只能执行第二种：y+=1变为偶数 当y为偶数，考虑将其变为y/2，那么直接除即可；如果变成y/2+1,第一种就是先除再加 1，操作为2步；否则就是加2然后再/2，操作为3步； 所以对于偶数的情况，先除再加更优； 那么整个解法就出来了：对于是偶数的就/2，对于y

#include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               using namespace std;const int maxn = 2010;typedef long long ll;#define rdint(x) scanf("%d",&x)#define inf 0x3f3f3f3fint x, y;int main(){ rdint(x); rdint(y); int minn = inf; int cnt = 0; while (1) { if (x == y)break; if (y % 2 == 0 && y > x) { cnt++; y /= 2; } else if (y > x&&y % 2 == 1) { cnt++; y += 1; } else if (y < x) { cnt += (x - y); y = x; break; } } cout << cnt << endl; system("pause");// return 0;}

转载于:https://www.cnblogs.com/zxyqzy/p/11128695.html

你可能感兴趣的文章