注意：如果您使用二分并且最后一个点WA了

有问题实时更新：https://www.luogu.com.cn/paste/109wv70a

如果您担心最终到了第

n

个点（或前面某一个点）却到不了终点（您可以理解为第

n + 1

个点），

那就多虑了，因为如果您从某一个点到达第

n

个点超过了二分的距离

mid

，那您难道不能强行拆掉第

n

个点，走到第

n + 1

个点吗，那么请问会影响最短跳跃距离吗？

然而我们为了方便就可以理解为把终点删掉了！（因为删除的数量相同，虽然题面中说不允许）

所以就有大多数题解中的

CPP

bool check(int x) {
    int last = 0, cnt = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (d[i] - d[last] >= x) last = i;
        else cnt++;
    }
    return cnt <= m;
}

即考虑

i = n + 1

时，如果

dis[i] - dis[last] < x

也删除第

i

个点，就是把终点删掉了，那么不就相当于删除前面的某一个点吗？

多个点的情况相同。

可以转化为

由此我们得出结论，如题解中的那样，在最后几个点中，碰到

\geq mid

可以直接跳到那里，不用考虑是否到达第

n + 1

个点，只是要枚举到第

n + 1

个点。

这样也就解释了为什么最后一个数据可以Hack。

这只是本蒟蒻的理解，如有不对，立删。

注意：如果您使用二分并且最后一个点WA了

讨论操作

回复

相关推荐

注意：如果您使用二分并且最后一个点WA了