题解 P5936【[POI 1999] 飞弹】

· · 题解

[POI 1999] 飞弹

审工单的时候口胡了一个做法，然后就把这题过了。把飞弹和地堡分别记为红点和蓝点，注意到这两种点是对称的。

首先有一个 naive 的想法：把所有点按照横坐标排序，然后找到一个分界线，使得左右两边红蓝点数差分别为 0。这样我们就可以强制让所有的匹配不越过这条中线，然后分治左右两边，这样做的时间复杂度是

\begin{aligned} T(n)&=T(a)+T(n-a)+\min\{a,n-a\}\\ &=\mathcal{O}(n\log n). \end{aligned}

边界条件是当只剩两个异色点时，直接匹配。但是这个做法是错的，因为满足性质的中线可能不存在。

然后我又有了一个 naive 的想法：求出凸包之后匹配凸包上异色的点，不断重复这个过程，不难发现每个匹配都是不交的。最坏情况是每找到一组匹配都要求一次凸包，所以这个做法的复杂度是 \mathcal{O}(n^2)。

当然这个做法也是错的，因为凸包上可能都是同一个颜色的点，但是此时的点集有一个特殊的性质：想法 1 中的中线一定存在。

证明如下：每次删去的都是一对匹配，因此红蓝点数相等，不失一般性令凸包上的颜色为蓝色。假想从左到右找中线的过程并对红蓝点数计数，一定有一个时刻红色的点先被遍历完，此时 蓝点个数 - 红点个数 一定小于 0，而在遍历到第一个红点时这个差一定是大于 0 的，根据零点存在性定理可知中线存在。\Box

最后把上面的两个算法拼起来就得到了一个正确的算法：先尝试寻找中线，如果找不到就匹配凸包上的边直到无法匹配为止，然后求出中线分治。

时间复杂度 \mathcal{O}(n^2)，代码很短就不放了。

当然这题还有（理论）更优的做法，火腿三明治定理（真的叫这个名字）告诉我们一定能在二维平面上找到一条直线能将两种颜色的点同时均分（注意可以是斜线），即直线两侧的红蓝点数均为 n/2。

Chi-Yuan Lo 和 William Steiger 于 1990 年给出了一种 \mathcal{O}(n) 寻找这条直线的算法，这直接导出了本题的 \mathcal{O}(n\log n) 做法。