1. 从一道集训题说起匹配星星到底在考什么第一次看到匹配星星这个题目名很多人会以为是个模拟题或者几何题实际上它是一道非常经典的贪心数据结构优化题目。题目的核心场景大致是这样的平面上有两类星星一类是普通星一类是特殊星每颗星星有自己的坐标和属性值要求把两类星星进行配对配对需要满足一定的偏序条件问最多能配出多少对。这类题在算法竞赛里出现的频率极高因为它的本质是二维偏序下的最大匹配问题。如果你只会写朴素的 O(n²) 暴力枚举数据量一大就直接超时而如果你能想到用排序消除一维、multiset 维护另一维就能把复杂度压到 O(n log n)稳稳过题。我当年第一次做这道题的时候卡了整整一个下午。不是因为贪心策略想不出来而是因为排序的关键字选错了导致后面无论怎么调 multiset 的查找逻辑都不对。后来复盘才发现这类题目的坑几乎都集中在三个地方排序维度、查找边界、以及删除时机。这篇文章我就把这道题从头到尾拆一遍把每一步为什么这么设计讲清楚让你以后遇到同类型的偏序匹配题能直接套思路。这篇文章适合谁看如果你正在刷算法基础集训营、准备校招笔试面试或者单纯想搞懂贪心multiset二分这套组合拳怎么用那这篇内容对你会有直接帮助。我会从题目建模讲起再到贪心策略的证明思路、multiset 的具体用法、二分查找的边界处理最后给出完整可复现的代码和几组实测数据。全程用大白话不堆术语保证你看完能自己写出来。2. 把题目翻译成数学模型二维偏序匹配2.1 题目条件的抽象过程先把题目里的自然语言翻译成数学语言。假设有 n 颗普通星和 m 颗特殊星每颗星星有两个属性我们记为 (x, y)。配对的条件通常是普通星的 x 小于特殊星的 x同时普通星的 y 小于特殊星的 y或者小于等于具体看题目。每颗星星只能用一次问最多能配多少对。这就是一个典型的二维偏序最大匹配。为什么叫二维偏序因为配对条件涉及两个维度的比较两个维度同时满足才能配对。如果只有一个维度那问题就退化成排序后贪心或者双指针简单得多。一旦升到二维就必须想办法降维。降维的核心思想是先按一个维度排序把这个维度变成有序的然后用数据结构维护另一个维度。这样每次处理时第一个维度天然满足只需要在第二个维度上做查找和匹配。2.2 为什么不能直接贪心有人会想那我直接对两类星星都按 x 排序然后双指针扫一遍不就行了问题在于x 满足条件的星星可能有很多颗它们的 y 值参差不齐。你如果随便挑一颗 y 最小的配对可能把 y 值浪费了——本来这颗普通星可以配给另一颗要求更低的特殊星结果你把它配给了一颗要求很高的导致后面有的普通星配不出去。举个具体例子。假设普通星有 A(1, 5) 和 B(2, 3)特殊星有 C(3, 4) 和 D(4, 6)。如果按 x 排序后先处理 C此时 A 和 B 的 x 都小于 3都满足第一维。C 的 y 要求是 4那么 A 的 y5 不满足5 不小于 4只有 B 的 y3 满足。所以 C 只能配 B。然后处理 DD 的 y 要求是 6A 的 y5 满足配 A。最终配成 2 对。但如果顺序反过来先处理 D 呢D 要求 y6A(1,5) 和 B(2,3) 都满足如果你贪心地选了 y 最小的 B 配给 D那 C 就只剩 A而 A 的 y5 不满足 C 的 y4结果只能配 1 对。这就是贪心选择错误导致答案变差的典型场景。所以正确的贪心策略不是随便挑一个满足的而是在满足第一维的前提下优先用 y 值最接近上限的那颗普通星去配也就是能配就配但要配得最节省。这个策略的严谨证明要用到交换论证我在下一节展开。2.3 降维后的处理框架把上面的思路整理成框架把两类星星放在一起按第一维比如 x排序。排序时要注意如果 x 相同特殊星要排在普通星后面因为普通星的 x 必须严格小于特殊星的 x不能相等。遍历排序后的序列遇到普通星就把它加入一个容器按 y 值有序遇到特殊星就在容器里找满足 y 条件且 y 值最大的那颗普通星配对成功后从容器里删除。容器需要支持插入、查找、删除而且都要高效。这就是 multiset 出场的地方。这个框架看起来简单但每一步都有细节。排序的 tie-break 规则、查找时用 upper_bound 还是 lower_bound、删除时删迭代器还是删值这些都会直接影响正确性。下面逐个拆。3. 贪心策略的证明为什么配最接近的是对的3.1 交换论证的直观理解贪心题最怕的就是感觉对但证明不了。这道题的贪心策略是对于每颗特殊星在满足条件的普通星里选 y 值最大的那颗配对。为什么这样最优用交换论证的思路。假设最优解里特殊星 S 配的是普通星 A但按我们的贪心策略应该配普通星 BB 的 y 比 A 大且都满足 S 的条件。那么在最优解里B 要么没被用要么配给了另一颗特殊星 S。如果 B 没被用那直接把 S 的配对从 A 换成 B配对数不变仍然是最优解。如果 B 配给了 S那我们把 A 和 B 的配对交换一下让 S 配 B让 S 配 A。关键问题是A 能不能满足 S 的条件因为 B 能满足 S 的条件B 原本就配给了 S而 A 的 y 比 B 小如果 S 的条件是 y 小于某个值那 A 的 y 更小只会更容易满足。所以交换后 S 配 A 仍然合法。配对数不变。通过不断交换任何最优解都能转化成每颗特殊星都配满足条件里 y 最大的普通星的形式所以贪心策略不劣于最优解。这就是交换论证的核心。3.2 为什么是y 最大而不是y 最小上面证明里有个关键点我们选的是 y 最大的。为什么因为特殊星的条件通常是普通星的 y 小于特殊星的 y也就是说普通星的 y 越小越百搭越容易满足后面的特殊星。所以我们应该把最百搭的y 最小的留到后面先用掉最不百搭的y 最大的。这跟先处理难的、把简单的留后面是一个道理。反过来如果你每次选 y 最小的配就等于把最百搭的先用掉了后面遇到条件苛刻的特殊星就没得配了。这就是 2.2 节例子里贪心失败的原因。3.3 第一维排序的 tie-break 陷阱排序时如果第一维相同怎么排这取决于题目条件是严格小于还是小于等于。如果条件是普通星 x严格小于特殊星 x那么 x 相同时普通星必须排在特殊星前面吗不对恰恰相反。因为普通星 x 不能等于特殊星 x所以当 x 相同时特殊星不能去匹配这些普通星。正确的做法是特殊星排在前面这样处理特殊星时x 相同的普通星还没被加入容器自然不会误配。如果条件是小于等于那 x 相同时普通星可以先加入特殊星排在后面。这个 tie-break 规则是很多人 WA 的根源。我当年就是这里搞反了样例能过但提交一直错调了半天才反应过来。建议你写完后专门构造一组 x 相同的测试数据验证一下。4. multiset 在这道题里到底扮演什么角色4.1 为什么不用普通数组或优先队列容器需要支持三种操作插入一个 y 值、查找满足条件里最大的 y、删除某个 y。普通数组插入和删除是 O(n)整体 O(n²)不行。优先队列堆只能取最大或最小没法做满足某个条件的最大也不行。multiset 是平衡树实现的插入、删除、查找都是 O(log n)而且它天然有序可以用二分查找定位到满足条件的边界。这正是我们需要的。有人会问用 vector 加二分行不行vector 插入删除是 O(n)虽然二分是 O(log n)但插入删除拖后腿整体还是 O(n²)。所以必须用平衡树结构C 里就是 multiset。4.2 multiset 的常用操作对照操作写法说明插入s.insert(y)插入一个值允许重复查找第一个大于等于 y 的位置s.lower_bound(y)返回迭代器查找第一个大于 y 的位置s.upper_bound(y)返回迭代器删除迭代器指向的元素s.erase(it)只删一个删除所有等于 y 的元素s.erase(y)删掉全部等于 y 的取最后一个元素prev(s.end())最大的元素这里有个大坑s.erase(y)会删掉所有等于 y 的元素而s.erase(it)只删迭代器指向的那一个。这道题里如果有多颗普通星 y 值相同你只想删一颗就必须用迭代器版本。我见过太多人在这里写错导致答案偏小。4.3 查找边界的确定假设特殊星的 y 是 Y条件是普通星 y 严格小于 Y。那么我们要在 multiset 里找小于 Y 的最大值。怎么找先auto it s.lower_bound(Y)这个 it 指向第一个大于等于 Y 的位置。那么it的前一个位置就是小于 Y 的最大值。如果it s.begin()说明没有小于 Y 的元素配不了。否则--it这个 it 就是我们要的。如果条件是小于等于 Y那就用upper_bound(Y)它指向第一个大于 Y 的位置前一个就是小于等于 Y 的最大值。这个边界处理是整道题最容易出错的地方。lower_bound 和 upper_bound 差一个等号结果可能完全不同。建议你拿纸画一下把严格小于和小于等于两种情况都推一遍。5. 完整代码实现与逐行注释5.1 数据结构定义#include bits/stdc.h using namespace std; struct Star { int x, y; int type; // 0 表示普通星1 表示特殊星 };用 type 区分两类星星方便统一排序。5.2 排序规则bool cmp(const Star a, const Star b) { if (a.x ! b.x) return a.x b.x; return a.type b.type; // x 相同时特殊星(type1)排前面 }这里a.type b.type保证 type1 的特殊星排在 type0 的普通星前面。对应 3.3 节讲的严格小于情况。5.3 主逻辑int main() { int n, m; cin n m; vectorStar stars; for (int i 0; i n; i) { int x, y; cin x y; stars.push_back({x, y, 0}); } for (int i 0; i m; i) { int x, y; cin x y; stars.push_back({x, y, 1}); } sort(stars.begin(), stars.end(), cmp); multisetint pool; int ans 0; for (auto s : stars) { if (s.type 0) { pool.insert(s.y); } else { auto it pool.lower_bound(s.y); if (it ! pool.begin()) { --it; pool.erase(it); ans; } } } cout ans endl; return 0; }5.4 关键行拆解auto it pool.lower_bound(s.y);找到第一个大于等于 s.y 的位置。if (it ! pool.begin())判断前面还有没有元素。如果 it 就是 begin说明所有元素都大于等于 s.y没有满足严格小于的。--it;退到小于 s.y 的最大值。pool.erase(it);用迭代器删除只删这一个。如果写成pool.erase(*it)就会删掉所有相同值这是错的。ans;配对成功计数加一。整个循环是 O((nm) log(nm))因为每个元素最多插入一次、删除一次每次操作 O(log n)。6. 实测踩坑记录那些让我 WA 到怀疑人生的细节6.1 坑一erase 删多了前面提过pool.erase(value)删所有等于 value 的元素。我第一次写的时候图省事直接pool.erase(*it)结果样例过了提交 WA。原因是样例里没有重复 y 值掩盖了这个问题。后来自己造了一组数据普通星 y 都是 5特殊星 y 都是 6正确答案是全部配对但我的代码只配了一对因为第一次 erase 就把所有 y5 删光了。记住multiset 删除单个元素必须用迭代器版本erase(it)删除值版本erase(val)是删全部。6.2 坑二排序 tie-break 反了前面 3.3 节讲过。我一开始写的是a.type b.type让普通星排前面。结果 x 相同的普通星和特殊星普通星先入池特殊星处理时就把不该配的配上了。改成a.type b.type后正确。这个坑的隐蔽性在于如果你的测试数据里 x 都不相同那怎么排都对根本发现不了。所以一定要专门构造 x 相同的数据。6.3 坑三lower_bound 和 upper_bound 混用题目条件是严格小于还是小于等于直接决定用哪个。我有一版代码把 lower_bound 写成了 upper_bound结果多配了一些本该配不上的对。判断方法很简单拿一个边界值测试比如特殊星 y5普通星 y5如果条件严格小于那配不上如果小于等于那能配上。跑一下就知道对不对。6.4 坑四迭代器失效在遍历 multiset 的过程中删除元素会导致迭代器失效。这道题里我们是在遍历 stars 数组时操作 pool不是在遍历 pool 本身所以没这个问题。但如果你写的是遍历 pool 边找边删就要小心。安全做法是先用一个临时迭代器记录位置删除后再重新定位。6.5 坑五数据范围导致的溢出如果坐标范围很大ans 用 int 一般够但如果题目要求输出配对数乘以某个系数可能溢出。养成习惯计数类变量用 long long除非确定范围很小。7. 从这道题延伸出去同类题目的通用套路7.1 二维偏序匹配的通用模板这道题的解法可以抽象成一个通用模板适用于一大类题目确定两个维度选择其中一个作为排序维度。按排序维度排序处理好 tie-break。用有序容器multiset、树状数组、线段树维护另一个维度。遍历时普通元素入容器查询元素在容器里找最优匹配并删除。这个模板能解决区间调度任务分配导弹拦截等一系列问题。区别只在于匹配条件的细节和容器的选择。7.2 什么时候该用树状数组而不是 multiset如果第二个维度的取值范围有限比如 y 在 1 到 10^5 之间可以用树状数组维护每个 y 值的出现次数查找时用树状数组上二分。这样常数更小速度更快。但如果 y 的范围很大比如 10^9就得先离散化或者直接用 multiset。multiset 的优点是写起来简单不用离散化缺点是常数比树状数组大。数据量在 10^5 级别时两者都能过10^6 级别时树状数组更有优势。7.3 如果题目变成三维偏序怎么办三维偏序就不能简单贪心了通常要用 CDQ 分治或者树套树。这是另一个话题但思路是一脉相承的先排序消一维再用数据结构处理剩下两维。如果你把这道二维的题吃透了三维的学起来会顺很多。7.4 贪心策略的验证方法写完贪心代码后怎么确认策略对两个办法对拍写一个 O(n²) 的暴力枚举随机生成小数据两个程序跑比对结果。如果几百组数据都一致基本可以放心。构造反例针对你的贪心策略尝试构造让它失败的数据。如果构造不出来说明策略可能确实对。对拍是算法竞赛里最实用的调试手段强烈建议养成习惯。我当年就是靠对拍发现了 erase 删多了这个 bug。8. 写在最后的一点个人体会这道题我前后做了三遍。第一遍看题解勉强写出来第二遍自己独立写还是卡在排序 tie-break 上第三遍才真正把每个细节都想明白。我的体会是贪心题不能只记结论一定要理解为什么。你知道选 y 最大的这个结论很容易但如果不理解交换论证遇到变体题就懵了。另外multiset 这个容器值得单独花时间练熟。它的 API 不多但每个都有坑尤其是 erase 的两个重载和 lower_bound/upper_bound 的区别。我建议你把这几个操作单独写个小程序跑一遍看看输出比看文档印象深得多。最后分享一个我自己的调试习惯每写完一道数据结构题我都会手动构造三组数据——一组全是重复值、一组边界值相等、一组极端大小。这三组能覆盖 80% 的边界 bug。这道题的三组数据分别是y 值全相同、x 值相同、n 和 m 都取最大。跑完这三组基本就能确定代码稳不稳了。