抓住那头牛

题目描述

农夫在数轴上的点 $N$ ，牛停在点 $K$ （ $0 \leqslant N, K \leqslant 100000$ ）。农夫每分钟可以从 $x$ 走到 $x-1$ 、 $x+1$ 或 $2x$ （位置不能为负），求走到 $K$ 的最少分钟数。

输入一行两个整数 $N$ 和 $K$ ，输出一个整数表示最小分钟数。

样例输入：5 17　样例输出：4（走法 5 -> 4 -> 8 -> 16 -> 17）。

思路

把每个坐标看成一个状态、三种操作看成边权为 1 的边，答案是 $N$ 到 $K$ 的最短路。边权全相等，用 BFS 从 $N$ 逐层扩展，首次访问 $K$ 时的层号就是最少分钟数。搜索范围限制在 $[0, 2K]$ ：越过 $2K$ 后回到 $K$ 至少要 $>K$ 步，不如从 $N$ 一路 +1 的 $K-N$ 步，所以更远的点不可能是最优。若 $K \leqslant N$ ，只有 -1 能下降，答案直接是 $N-K$ 。

参考代码

Python 版：

python

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
31
32
33
34
35
36
37
38
39#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:14
# update_at: 2026-09-30 02:21

import sys
from collections import deque


def shortest_time(n: int, k: int) -> int:
    """农夫从 n 到 k 的最少分钟数：边权全为 1 的最短路 = BFS 第一次到达。"""
    if k <= n:
        # 每步向下最多减 1（+1 与 ×2 都不降），t 步后位置 ≥ n-t，
        # 故到 k 至少需 n-k 步；一路 -1 恰好达到。
        return n - k
    limit = 2 * k  # 上界：越过 2K 的位置 x 回到 K 至少要 x-K>K 步，不如直线走法的 k-n 步
    dist = [-1] * (limit + 1)  # -1 兼作"未访问"标记
    dist[n] = 0
    frontier = deque([n])
    while frontier:
        x = frontier.popleft()
        for y in (x - 1, x + 1, 2 * x):
            if 0 <= y <= limit and dist[y] < 0:
                dist[y] = dist[x] + 1
                if y == k:
                    return dist[y]  # 逐层扩展，首次到达即最少分钟数
                frontier.append(y)
    return dist[k]


def solve() -> None:
    n, k = map(int, sys.stdin.buffer.read().split())
    print(shortest_time(n, k))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:02
 * update_at: 2026-10-05 07:02
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXK = 100005;

ll N, K;

int dist[2 * MAXK + 5]; // dist[x] 表示从 N 到坐标 x 的最少分钟数，-1 兼作“未访问”标记
queue<ll> bfs_queue;    // 待扩展的坐标

// 把坐标看成点、三种操作看成长度 1 的边，问题就是无权图上 N 到 K 的最短路。
// BFS 逐层扩展，第一次到达的层号即为最短距离。
ll bfs() {
    ll limit = 2 * K; // 上界：越过 2K 后想回到 K 至少要走 > K 步，不如从 N 一路 +1 的 K-N 步
    for (ll x = 0; x <= limit; x++) {
        dist[x] = -1;
    }
    dist[N] = 0;
    bfs_queue.push(N);

    while (!bfs_queue.empty()) {
        ll x = bfs_queue.front();
        bfs_queue.pop();

        // 三种操作：走到 x-1、x+1、2x
        ll nxt[3];
        nxt[0] = x - 1;
        nxt[1] = x + 1;
        nxt[2] = 2 * x;

        for (int i = 0; i < 3; i++) {
            ll y = nxt[i];
            if (y < 0 || y > limit) continue;
            if (dist[y] >= 0) continue;
            dist[y] = dist[x] + 1;
            if (y == K) return dist[y]; // 逐层扩展，首次到达即最少分钟数
            bfs_queue.push(y);
        }
    }
    return dist[K];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;

    if (K <= N) {
        // 向下的操作只有 -1（+1 与 *2 都不降），故答案就是一路减过去
        cout << N - K << "\n";
        return 0;
    }

    cout << bfs() << "\n";
    return 0;
}

目录

题目描述

思路

参考代码