如果一道题没有给出顶点和边，能不能用图算法？可以：把“当前局面”当作顶点，把“一次合法操作”当作有向边，最少操作次数就变成了最短路。

这篇用一道题走两遍：先用 BFS 建立可靠的通用解法，再利用操作的特殊结构，把搜索压缩成逆向贪心。重点不是背两份代码，而是分清哪个结论来自图模型，哪个结论必须另行证明。

1. 先确定状态与边

520B · Two Buttons 官方题目 的难度为 1400；官方标签包括 graphs、shortest paths、greedy、math、implementation、dfs and similar，于 2026-09-07 核对。下面是原创推导，不复述题目故事。

起点为正整数 n，目标为正整数 m。每步可以把当前数乘 2，或减 1；过程中不能变成 0 或负数。官方输入满足 1≤n,m≤10000 且二者不同；本文实现也自然支持相等时返回 0。

图中的概念 本题对应
顶点 x 当前显示的正整数
有向边 x → 2x；当 x>1 时还有 x → x-1
边的代价 一次操作，均为 1
目标 从 n 到 m 的最短路径长度

只记录当前值就足够了：未来能执行什么操作，与之前怎么到达这个值无关。若再加上“翻倍最多能用两次”，状态就必须记录已用次数，不能继续只用 visited[x]。

2. 离目标更近，不等于剩余步数更少

看 n=4，m=6：先翻倍得到 8，之后需要两次减法；先减到 3，再翻倍就到达目标。

这张图只画两条候选路径，不是完整状态图。上路 3 步，下路 2 步。“只要还没到目标就翻倍”没有最优性保证，数值距离也不是操作距离。

BFS 为什么得到最短路

BFS 用队列按步数逐层扩展。设 dist[x] 为第一次发现 x 时的步数，起点距离为 0，未访问位置为 -1。

层数 本例首次发现的状态 含义
0 4 尚未操作
1 8、3 一步可达
2 7、6、2 两步首次到达；16 超出下节证明的搜索界限

边权都等于 1，因此队列中先处理完距离 d 的状态，才会处理距离 d+1 的状态。第一次发现目标时，不可能还存在一条没有探索到的更短路径。

入队时就设置距离，不要等出队才标记。这样相同状态即使由不同路径产生，也只入队一次。普通 DFS 先找到的路径则未必最短。

3. 数字可以无限大，数组为什么可以有限长

设 B=2×max(n,m)，只搜索 [1,B]。这个上界需要证明，不能仅凭“开两倍应该够”。

  • 若 n≥m，直接减到 m 用 n-m 步。翻倍只会增加之后必须抵消的数值，不可能减少步数。
  • 若 n<m，考虑一条路径第一次到达不小于 m 的数 y。这一步只能是从某个 x<m 翻倍而来，所以 y=2x≤2m-2。
  • 一旦到了 y≥m，最优后缀就是连续减一。每次减法只能减 1，而翻倍会额外增加当前正整数大小；插入翻倍只会增加所需减法和总操作数。

所以总能找到一条最优路径：首次越过目标前小于 m，越过时不大于 2m-2，之后单调减到目标。没有必要探索更大的数。本例 B=12，因而舍弃 16 不会错过最优解。

BFS 的 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    const int bound = 2 * max(n, m);
    vector<int> dist(bound + 1, -1);
    queue<int> q;
    dist[n] = 0;
    q.push(n);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == m) {
            cout << dist[x] << '\n';
            return 0;
        }
        for (int next : {x * 2, x - 1}) {
            if (next < 1 || next > bound || dist[next] != -1) continue;
            dist[next] = dist[x] + 1;
            q.push(next);
        }
    }
}

共有 B 个候选状态，每个最多检查两条边；时间与额外空间均为 O(B)。在本题范围内，int 足以保存状态与距离。若把输入扩展到极大整数，既要重审乘法溢出，也要重审数组规模。

4. 倒着走，选择反而更少

把边反向：从 m 回到 n，可执行“加 1”和“偶数除以 2”。这是反向图上的路径，不是在偷偷更换原题允许的操作；把整条路径倒过来，就恢复原来的减一和翻倍。

当当前值 y>n 时：

  1. y 为奇数，不能除以 2，下一步只能加 1。
  2. y 为偶数，可以立即除以 2；为什么它优于先加几次，需要交换论证。

偶数时立即减半的证明

因为 y>n，仅靠加一不可能回到更小的 n，所以任何成功路径迟早要执行一次除二。从偶数出发，这次除二之前必定加了偶数次，记作 2r 次。

到达相同状态 y/2+r 的两种前缀 操作数
先加 2r 次，再除二 2r+1
先除二，再加 r 次 r+1

第二种前缀始终合法，并且不更长；当 r>0 时还严格更短。后面的路径可以原样接上，所以总有最优解在偶数处立即减半。

当 y≤n 时，直接加 n-y 次即可。任何除二都会使数值更小，增加需要补回的加法，不可能更优。

手算一次逆向过程

取 n=3，m=10：

当前值 决策 累计步数
10 偶数且大于 3，除二得到 5 1
5 奇数，加一得到 6 2
6 偶数且大于 3，除二得到 3 3

反转路径得到 3 → 6 → 5 → 10，每一步都是原题合法操作。注意判断顺序：先看是否已不大于起点，再看奇偶，不能对所有偶数无条件除二。

逆向贪心的 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int steps = 0;
    while (m > n) {
        if (m % 2 == 0) m /= 2;
        else ++m;
        ++steps;
    }
    cout << steps + n - m << '\n';
}

在循环中，偶数一步减半；奇数至多两步变成原值的一半向上取整。因此时间为 O(1+log m)，这里的 m 指原始目标值；额外空间 O(1)。n≥m 时直接常数时间结束。

5. 两种算法分别教会了什么

问题 BFS 逆向贪心
核心依据 单位边权与分层搜索 奇偶约束与交换论证
是否保留备选状态 是，用距离数组去重 否，每步选一个方向
怎样还原具体操作 首次入队时记录父状态，再回溯 记录逆向经过的值，再反转
修改操作规则后 重建图、重证边界后可能仍适用 必须重新证明局部选择

这也能与 一维动态规划 对照：Cut Ribbon 的前驱长度严格更小，可以按长度顺序递推；本题状态图含有 1 → 2 → 1 这样的环，直接按数值从小到大填“最少步数”并不能保证依赖已算好。

BFS 的适用条件同样不能省略：若两种操作代价不同，首次发现不再必然最优。可以继续读 20C：Dijkstra 与路径还原，学习正权图的通用处理；若边权只取 0 和 1，则可进一步考虑 0-1 BFS。

6. 不只检查两个样例

n、m 最少步数 检查意图
4、6 2 先减再乘
10、1 9 起点大于目标
1、3 3 1 不能再减一
3、10 3 逆向奇偶交替
5、8 2 减半后小于起点，需要补差
9999、10000 5000 目标接近，也可能需要很多步
7、7 0 官方约束外的防御性扩展

对拍时可以为每个小起点建立一次 BFS 距离表，逐个比较目标值的贪心答案；还可以把搜索上界扩大到四倍，检查小范围答案是否变化。但有限测试不能代替上界证明：真正保证所有输入都成立的，仍是第 3 节的越界与后缀论证。

练习时先独立完成 BFS，再遮住第 4 节尝试证明逆向选择。若只能写出“偶数就除二”，却不能解释为什么不先加二，还没有完成贪心解法最重要的一步。

接下来可回看 贪心三题的不同证明方式，或沿 算法练习路径 比较搜索、动态规划与答案二分各自利用的结构。