(CF520B)Two Buttons
思路:
贪心
若 \(m\) 为偶数,则将 \(n\) 变为 \(m/2\), 否则变为 \(\(m+1\)/2\), 然后递归求解
下面简单说明为何这个方案是最优方案:
假设 \(n > \frac{m}{2}\), 且 \(m\) 为偶数,有两种方案将 n 变为 m:
\(n*2\), 然后减到 m
\(n\) 减到 \(\frac{m}{2}\), 然后乘 2
假设 \(n = \frac{m}{2} + x\), 则:
方案 1 所需步骤为 \(2x+1\)
方案 2 所需步骤为 \(x+1\)
显然方案 2 更优.
若 \(m\) 为奇数,则将上面的 \(m\) 改为 \(m+1\), 同样能得到方案 2 更优的结果
若 \(n < \frac{m}{2}\), 则将 \(m\) 变为 \(\frac{m}{2}\), 可使得每次的 \(x\) 最小
代码:
1 |
|