问题: 边界条件的考虑方式, 权值相等时, 第二关键字应该是最大化还是最小化.
用 hzwer 的选 \(k\) 个白点那道题来说吧, 给每个白点增加 \(mid\) 的权值, 计算 MST 的白点数量 \(cnt\) .
\(mid\) 增大, \(cnt\) 减小, 二分大概长这样:
- while (l <= r) {
- cnt = check(mid);
- if (cnt <= k) {
- // update ans
- r = mid - 1;
- } else {
- l = mid + 1;
- }
- }
类似一个单调不升的序列, 二分一个值, 最后肯定是停在一段连续相同的值的左边 (因为 \(cnt = k\) 的时候还在减小 \(mid\) ).
如此能保证的只有 \(mid - 1\) 位置的 \(cnt> k\) , 它是非法的.
这种非法情况, 应该无论如何都非法. 就是说 \(mid - 1\) 位置对应的各种 \(cnt_{min}, \cdots, cnt_{max}\) , 都大于 \(k\) (否则合法的情况就可能在 \(mid - 1\) 位置, 这时候该选 \(mid\) 还是 \(mid - 1\) 就说不清了), 所以应该保证 \(cnt_{min}>k\) 才正确.
说完了.
具体放到题里面, 求 \(cnt\) 时, 点权相同时, 最小化 \(cnt\) . 反过来说有人二分里面更新答案时用的是 cnt>= k , 那就应该优先选白点, 计算 \(cnt_{max}\) .
似乎大佬们有不同的解释, 不过暂时我只能这样理解, 似乎没什么问题. 八省联考 2018 林克卡特树 也是这个方式考虑第二关键字 (没有这个东西, 是我口胡的).
来源: http://www.bubuko.com/infodetail-2964396.html