题解：AT_agc032_e [AGC032E] Modulo Pairing

· · 题解

好题！

套路的考虑排序后画出连线，则发现不劣的匹配一定形如如下形式：（蓝色是 <m，红色是 \ge m）

（这个图是贺的）

证明考虑调整法。具体的，枚举四个点之间的匹配方式，则最后的不劣形式一定形如前两个匹配蓝后两个匹配红，或者嵌套着匹配同色对。此处不再赘述。

考虑枚举分界点，则复杂度为 O(n^2)，过不去。

如何优化？考虑蓝其实不用满足 x+y<m，反正这样答案变大又不是变小。

所以我们尽量靠左，但是右边的红还是有限制的。连续的限制考虑二分，则此题得解。