「这个题有O(nlogn) 解法吧」 - 洛谷帖子保存站

这个题有O(nlogn) 解法吧

板块P1991 无线通讯网
楼主damocris
当前回复2
已保存回复2
发布时间2022/1/12 08:35
上次更新2023/10/28 12:29:48

被骇客银狼阻止的越权访问保存失败

这个题有O(nlogn) 解法吧

damocris楼主2022/1/12 08:35

先用平面欧几里得距离的最小生成树，用delauney三角剖分可以做到O(nlogn)，然后划分求第k大是O(n)的。总复杂度O(nlogn)

2022/1/12 08:35