自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:59，当前版本为作者最后更新于2025-03-05 10:45:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

假设你要踩着河里的石头过河，每次都想尽可能跨最大的步子，这样总步数就会最少——这正是贪心算法的精髓所在。

一开始，我们从起点（坐标 $0$）出发，此时跳跃次数为 $0$。需要观察前方有哪些石墩在可跳跃范围内（即距离不超过 $M$ 米）。

每次跳跃时，在所有可以跳到的石墩中，果断选择最远的那个。这样做不仅能最大限度缩短剩余距离，还能减少后续需要决策的次数。例如当前在坐标 $5$，能跳到 $8$ 和 $10$ 两个石墩，选择 $10$ 显然更有利于后续跳跃。

当最后一次跳跃时，可能出现两种情形：要么从某个石墩直接跳到对岸，要么需要额外计算这次跨越。比如最后停留的石墩距离对岸还有 $3$ 米，而最大能跳 $5$ 米，这时只需要再加一次跳跃即可。

参考代码（只展示关键部分）：

int ans = 0, pos = 0; // pos 表示当前所在位置
int i = 0; // 用于遍历石墩数组
while (pos + M < L) {  // 若当前能跳到的位置不足以到达对岸
    int next = pos;
    // 从当前位置出发，找到所有能跳到的石墩中最远的一个
    while (i < N && d[i] <= pos + M) {
        next = d[i];
        i++;
    }
    // 如果找不到更远的落脚点，跳跃就无法进行
    if (next == pos) break;
    pos = next; // 更新当前位置
    ans++;    // 跳跃次数加一
}
// 最后一次从石墩或起点跳到对岸
if (pos < L) ans++;
cout << ans;