跳石头

二分最短的跳跃距离 $x$，将问题转为判定性问题。

即给你一个跳跃的最短距离，你来求需要移走几个岩石，不超过 $M$，这个距离就合法。

遍历所有的石头，维护上一个呆的位置，现在你准备从上一个位置跳到 a[i]

若从上一个位置 last 跳到 a[i]，二者的距离小于 $x$，说明第 $i$ 个需要移走，因为我们需要保证最短的跳跃距离至少为 $x$。

否则不需要移走，就更新上一个石头的位置。

int last = 0, ans = 0;
for (int i = 1; i <= n + 1; i++)
{
    if (a[i] - last < x)
        ans++;
    else
        last = a[i];
}
if (ans <= m)
    return 1;
return 0;

注意最后需要从第 $n$ 个跳到终点，因此新增一块石头 a[n + 1] = L

[TJOI2007] 路标设置

考虑二分空款指数，检验新增个数是否不超过 $k$ 即可，其满足单调性，随着最大空旷指数的减小，新增的个数必然越来越多。