正经题解｜抓住那头牛

【算法分析】

由于位置的个数很少且要求最小步数，可以考虑从 $n$ 位置开始广搜，同时用一个数组 $d$，$d_i$ 表示从 $n$ 位置到 $i$ 位置需要的步数，最后输出 $d_k$ 即可。

【参考代码】

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 9;
int d[maxn];
int main() {
    int n, k;
    cin >> n >> k;
    memset(d, -1, sizeof(d));
    d[n] = 0;
    queue<int> q;
    q.push(n);
    while (q.size()) {
        int r = q.front();
        q.pop();
        if (r >= 1 && d[r - 1] == -1) {
            d[r - 1] = d[r] + 1;
            q.push(r - 1);
        }
        if (r < 1e5 && d[r + 1] == -1) {
            d[r + 1] = d[r] + 1;
            q.push(r + 1);
        }
        if (2 * r <= 1e5 && d[2 * r] == -1) {
            d[2 * r] = d[r] + 1;
            q.push(2 * r);
        }
    }
    cout << d[k];
    return 0;
}

【时间复杂度】

$O(1e5)$

【预计得分】

$100pts$