题解：CF2122C Manhattan Pairs

· · 题解

差点被这奶龙给创飞了导致差点渡劫失败，吓死我了。

我们先考虑一维。

一维等价于数轴上有 n 个点，选 \frac n2 个连线段。

很显然，你先排序，前面一半的集合直接匹配后面一半即可。

考虑扩展。

充分发挥人类智慧，猜测 x,y 互不影响。

那么就有做法：按 x 排序，前后两半都按 y 升序排序，然后 i 匹配 i+\frac n2。

然后就 A 了。

:::success[证明]

定义 \operatorname{mid}(x_{1\sim n}) 为 x 的中位数。

注意到假如有一条 x=\operatorname{mid}(x_{1\sim n}) 的直线和有一条 y=\operatorname{mid}(y_{1\sim n}) 的把平面划分成 4 各部分，那么左上的部分和右下的部分点数相等，右上的部分和左下的部分点数相等。

那么根据刚刚的结论，最优就是对角部分的点互相匹配。而对角部分点数相等，因此得证。 :::