寒假Day51:Codeforces520BTwo Buttons思维/bfs

题目链接:http://codeforces.com/problemset/problem/520/B

 
题意:给出n和m,问从n变到m最少需要几步(有两种操作:乘2或者减1)
 
思路:本来想着贪心做的,但是失败了。
后来直接简化代码,从m入手,判断m的奇偶,如果为奇数,则n无法通过乘2变成m,所以需要m++;
如果m为偶数,说明n可以到m,所以m/2即可。
当n大于等于m的时候跳出循环,所以最后还要加上n-m的差。
 
AC代码:
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // red*2、blue-1
    //n->m
    int n,m;
    while(cin>>n>>m)
    {
        int ans=0;
        while(n<m)
        {
            if(m%2)
                m++;
            else
                m/=2;
            ans++;
        }
        cout<<ans+n-m<<endl;
    }
    return 0;
}
这道题目查了题解发现暴力可以解决,我的暴力应该少了考虑因素;
这一题还可以用bfs写,我觉得简单题目简单写,不要想太复杂了,
但是我觉得这一题稍微数据给大一点,就应该从bfs入手;
当类似此题给出的数据大,且又是求最短次数,应该会有一个方向就是bfs。
 
原文地址:https://www.cnblogs.com/OFSHK/p/12500970.html