PointyWizardHats

作者：辜俊儒 钟知闲 徐明宽

关键字：二分图匹配 贪心

题目简述

给出两组圆锥形的帽子，每个帽子有一个高度 $h$ 和半径 $r$ ；

第一组中的帽子能放在第二组中的帽子上组合成一个新的帽子需满足：

1. 两帽子的端点不相碰
2. 第二组中的帽子不会被完全覆盖

最大化组合成的新帽子的个数。

每组中的帽子个数$\leq 50$

解题思路

两帽子能配对，需满足$h1/r1 > h2/r2, r1 < r2$；

跑二分图最大匹配即可。

复杂度$O(n^3)$。

另一种解法

对于该问题，有一种时间复杂度和代码实现难度上都优于二分图匹配的解法。

首先我们将所有的帽子按照 $\frac{h_i}{r_i}$ 从大到小排序，然后按顺序将每个第二组的帽子 $i$ 与第一组中 $i$ 能匹配的帽子中 $r_j$ 最大的一个 $j$ 匹配。

为什么这样贪心是对的？

假设最优方案中第二组的第 $1$ 个帽子 $x$（已按 $\frac{h_i}{r_i}$ 从大到小排序）没有按贪心策略匹配，那么将 $x$ 改成和第一组中它能匹配的 $r_j$ 最大的帽子 $j$ 匹配，如果 $j$ 被另一个第二组的帽子 $i$ 匹配了，有两种情况：（1）原先 $x$ 没有和任何第一组的匹配，则直接去掉 $i$ 的匹配；（2）原先 $x$ 和 $y$ 匹配，则将 $i$ 改成和 $y$ 匹配，由于 $\frac{h_y}{r_y}\ge\frac{h_x}{r_x}\ge\frac{h_i}{r_i}$，且 $r_y\le r_j\le r_i$，这样的匹配一定是成立的。并且修改后的匹配数不会变少，因此按照该贪心策略可以得到最优解。

实现时，先将所有帽子按 $\frac{h_i}{r_i}$ 从大到小排序，然后建立一个集合 $S$ 和答案变量 $s$（初始 $s = 0$），按顺序考虑每个帽子 $i$，如果属于第一组，就加入 $S$，如果属于第二组，就从 $S$ 中查找 $r_j$ 比 $r_i$ 小且 $r_j$ 最大的 $j$，如果找到，就将其从 $S$ 中删去并将 $s$ 增加 $1$，没找到则 $s$ 不变。最后 $s$ 就是答案。

使用 C++ 的 STL 中的 multiset 可以高效完成集合插入及查找操作，复杂度 $O(n\log n)$，代码仅不到 $800\texttt{B}$，十分简洁。