题解：P15541 [CCC 2026 S1] Baby Hop, Giant Hop

yingMC · 2026-03-05 19:30:59 · 题解

::::info[题意]

青蛙从 A 跳到 B，可跳 1 格或 K 格，可前可后。求最少跳跃次数（T=1）或第二少跳跃次数（T=2）。

:::: ## 思路设 $D = |A-B|$，$q = \left\lfloor \dfrac{D}{K} \right\rfloor$，$r = D \bmod K$。 ### 最少步数 - 用 $q$ 次大跳，再小跳 $r$ 次：$q+r

用 q+1 次大跳，再往回小跳 K-r 次：q+1+K-r
最少步数取较小值： \text{ans}_1 = \min(q+r,\; q+1+K-r)

第二少步数

可能来自：

在最少方案基础上多做两次来回跳：\text{ans}_1+2
取 n = q-2,\;q-1,\;q,\;q+1,\;q+2,\;q+3 计算 f(n)=|n| + |D - nK|，取大于 \text{ans}_1 的最小值
两者中较小的即为答案。

特判 D=0：最少 0，第二少 2。(~~应为它错了几次了~~)

代码

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

int main() {
    long long a, b, k;
    int T;
    cin >> a >> b >> k >> T;
    long long D = llabs(a - b);

    if (D == 0) {
        cout << (T == 1 ? 0 : 2) << endl;
        return 0;
    }

    long long q = D / k, r = D % k;
    long long ans1 = min(q + r, q + 1 + k - r);

    if (T == 1) {
        cout << ans1 << endl;
        return 0;
    }
    long long ans2 = ans1 + 2; // 候选1
    // 检查附近几个 n
    for (long long n = max(0LL, q - 2); n <= q + 3; ++n) {
        long long val = llabs(n) + llabs(D - n * k);
        if (val > ans1 && val < ans2) ans2 = val;
    }
    cout << ans2 << endl;
    return 0;
}

求赞！