题解：P10768 「CROI · R2」落月摇情

__liujy · 2026-08-09 19:50:46 · 题解

P10768 「CROI · R2」落月摇情

为表述方便，在下文中的正数也包含 0。

注意到 0 \le |a_{i}| \le 10^{6}，这启示我们要对 a_{i} 的正负性进行分讨。

在下文中，默认 \{ a\} 单调不降。

在下文中，L 分讨代表对 \{ a\} 是否都是全负或者全正或者有正有负进行分讨。

考虑当 a_{i} < 0 时，对于点 i 建一条 i 到 n 的边一定是最优的；否则，对于点 i 建一条 i 到 1 的边一定是最优的。L 分讨一下，不难得出，这么做图一定是联通的，并且一定有自环或者重边，并且这样的只有 1 组，即要么有一条重边，要么有一个点构成自环，所以只要把其中的一条边删去即可，最后得到的就是这张图的最小生成树，这样就解决了 m = n - 1 时的问题。

剩下还有 m - (n - 1) 条边要选，选的条件是尽可能权值下并且和之前的没有重复。显然的，选的这些边的权值的最大值是有最大值的，并且对于 k 与 k+1，小于等于 k 的边的数量一定不会小于小于 k+1 的，即具有单调性，这启示我们可以二分这些边的最大值 k，找到最小 k，使得小于等于 k 的边的大于等于 m - (n - 1)，这个过程里记得判有没有在之前的最小生成树中。

考虑怎么统计答案。设最后选出的 k 为 v。对于所有权值小于 v 的边一定都选，不然与二分出来的答案的性质相冲突，对于权值等于 v 的边只要在选完所有权值小于 v 的边后还不够 m - (n - 1) 才选。

在二分的 check 中，可以直接暴力枚举，根据 a_{i} 的正负性决定是正序枚举还是倒序枚举 j，这样 a_{i} \times a_{j} 显然具有单调性，如果当前 a_{i} \times a_{j} > k 就直接退出循环，只要当前的边数大于等于 m - (n - 1) 就直接返回 true，这样时间复杂度不会爆炸，很容易证明。统计答案同理。

这样做时间复杂度为 O(m \log V)。