注意:如果您使用二分并且最后一个点WA了
查看原帖
注意:如果您使用二分并且最后一个点WA了
520333
SunnyYuan楼主2023/2/18 12:20

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

如果您担心最终到了第 nn 个点(或前面某一个点)却到不了终点(您可以理解为第 n+1n + 1 个点),

那就多虑了,因为如果您从某一个点到达第 nn 个点超过了二分的距离 midmid ,那您难道不能强行拆掉第 nn 个点,走到第 n+1n + 1 个点吗,那么请问会影响最短跳跃距离吗?

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

所以就有大多数题解中的

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+1i = n + 1 时,如果 dis[i]dis[last]<xdis[i] - dis[last] < x 也删除第 ii 个点,就是把终点删掉了,那么不就相当于删除前面的某一个点吗?

多个点的情况相同。

可以转化为

由此我们得出结论,如题解中的那样,在最后几个点中,碰到 mid\geq mid 可以直接跳到那里,不用考虑是否到达第 n+1n + 1 个点,只是要枚举到第 n+1n + 1 个点。

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

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

2023/2/18 12:20
加载中...