Codeforces 520B Two Buttons：貪心逆向思維

題目

兩個按鈕：紅鈕 ×2，藍鈕 -1。從 n 變到 m (1 ≤ n,m ≤ 10^4)，求最少按鈕次數。若中途 ≤0 則失敗。

核心觀察

正向 BFS 可行但過殺。逆向思維：從 m 反推到 n。
• 若 m ≤ n：只能藍鈕（正向紅鈕），答案 n-m。
• 若 m > n：
- m 為偶數 → 反操作 ÷2（對應正向 ×2），步數+1。
- m 為奇數 → 反操作 +1 再 ÷2（對應正向 -1 後 ×2），步數+2。
循環直到 m ≤ n，最後加上 n-m。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    int ans = 0;
    while (m > n) {
        if (m % 2 == 0) m /= 2, ans++;
        else m = (m + 1) / 2, ans += 2;
    }
    ans += n - m;
    cout << ans << endl;
    return 0;
}

複雜度

每步 m 至少減半，O(log m) 時間，O(1) 空間，極其高效。