NFLSPC #2 Magic 题解

2019-11-29 16:44:15 By wzy

先转曼哈顿,如果所有点的 $y=0$ 的话,那么任意一个匹配必然都经过 $x$ 的中位数(最大值的充要条件)。

取 $x$ 坐标的中位数 $a$ 和 $y$ 坐标的中位数 $b$ 得到点 $(a,b)$,然后以这个点为中心划分成一个十字,左上和右下匹配,左下和右上匹配即可。

假设 $n=2k$ 为偶数,那么左半边和右半边都有 $k$ 个,上半边和下半边也都有 $k$ 个。设左上有 $p$ 个,则右下有 $k-(k-p)=p$ 个,可以进行一一匹配;同理,左下也可以和右上进行一一匹配。

$n$ 为奇数时就记一下两维的前缀和,暴力计算出最优解应该删掉哪个点即可。复杂度瓶颈在 sort 上,$O(n \log n)$。

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。