蓝桥杯国赛冲刺 -- cf刷题记录 -- 520B. Two Buttons贪心

Two Buttons

• 题目描述
• 大致题意
• 思路
• 代码

题目：Two Buttons
难度：*1400
标签：贪心，dfs，bfs，最短路，模拟
该篇文章使用贪心实现（python）

题目描述

大致题意

给你两个整数n，m，每次可以在两次 *** 作中选择一个 *** 作：

1. 将 n 乘以 2
2. 将 n 减去 1

问最少需要多少次 *** 作可以使得 n == m

思路

乍一看最小 *** 作次数，首选方法bfs，但是该题数据量过大，不适宜用bfs。

可以尝试考虑贪心的思路。

可以看出可选择的 *** 作没有除，所以如果 n 比 m 大只能 一直减一。
选哪种 *** 作最划算呢？
看样子得多用乘法比较划算，我问当然希望能一路乘到结果，但是这样的话n得是m的二分之一，四分之一，八分之一…
但是我们不好权衡是乘了之后再减还是减了之后再乘。

不妨逆向思考一下，我们用m得到n，每次m除以二或者是加一，这样一来我们就能一直除，直到m不大于n为止。
如果m为奇数，加一，否则除以二

代码

a, b = list(map(int, input().split(" ")))

ans = 0
while a < b:
    if b % 2 == 1:
        b += 1
        ans += 1
    b //= 2
    ans += 1
ans += a - b
print(ans)