B4089 [CSP-X2020 山东] 勇敢的津津

· · 题解

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

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

一开始，我们从起点（坐标 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;