★ FEATURED ARTICLE 1. 从一道集训题说起匹配星星到底在考什么第一次看到“匹配星星”这个题目名很多人会以为是个图形学或者游戏相关的题实际上它是一道非常典型的贪心加数据结构优化题。题目的核心场景是这样的平面上有两类星星一类是“主星”一类是“辅星”每颗星星都有自己的坐标和属性值。你需要把辅星和主星进行配对配对需要满足若干维度的约束条件比如坐标范围、属性值大小关系等最终要求最大化匹配数量或者最小化某种代价。这道题出现在算法基础集训营里定位是“基础”但实际做下来会发现它考察的东西一点都不基础。它把贪心策略的设计、multiset 的灵活运用、二分查找的边界处理这三个技能点揉在了一起。如果你只是会写一个排序加遍历大概率会卡在超时或者答案错误上。我带过不少刚接触算法竞赛的同学他们在这道题上踩的坑非常集中要么贪心策略选错了方向要么用数组硬模拟导致复杂度爆炸要么二分的时候左右边界搞反了。这篇文章我会从零开始把这道题的完整思考过程拆开来讲。不管你是正在刷牛客题单的选手还是想系统提升贪心加数据结构能力的开发者都能从里面拿到可以直接复用的东西。我会先讲清楚题目背后的约束模型然后一步步推导为什么贪心可行、为什么选 multiset 而不是别的容器、二分到底在二分什么最后给出完整的代码实现和几组实测数据。中间还会穿插我在实际做题和教学过程中总结的避坑经验这些是你在标准题解里不太容易看到的。2. 题目约束建模把故事翻译成数学语言2.1 星星属性的抽象与形式化先把题目里的“星星”翻译成计算机能处理的数据。假设有 n 颗主星和 m 颗辅星每颗星星有两个关键属性一个是位置相关的值记为 x另一个是能力相关的值记为 y。匹配规则通常是这样的一颗辅星能和一颗主星配对当且仅当辅星的 x 小于等于主星的 x并且辅星的 y 小于等于主星的 y。目标是在所有可能的配对中找到最大的匹配数量。这个模型和经典的“任务分配”问题非常像。你可以把主星想象成一台机器有两个参数最大承受位置和最大承受能力辅星想象成一个任务有两个需求参数。任务能被机器处理的条件是两个需求都不超过机器的上限。我们要做的就是尽可能多地把任务分配出去。为什么这个抽象很重要因为一旦你把它看成任务分配问题就会自然联想到一个经典结论当有两个维度的约束时先按其中一个维度排序然后在另一个维度上用贪心加数据结构来优化。这个思路是解决这类问题的通用套路不只是这一道题。2.2 为什么不能简单排序后双指针有些同学第一反应是把主星和辅星都按 x 排序然后用两个指针扫一遍能配就配。这个思路在只有一个维度的时候是对的但这里有两个维度。我举个例子说明为什么不行。假设主星有两颗A(x10, y100)B(x20, y5)。辅星有两颗C(x5, y6)D(x15, y4)。如果按 x 排序后双指针贪心可能会先用 C 去匹配 A因为 A 的 x 更大看起来“更能容纳”。但 C 的 y6 大于 B 的 y5所以 C 只能匹配 A。然后 D 的 x15 大于 B 的 x20不15 小于 20但 D 的 y4 小于等于 B 的 y5所以 D 可以匹配 B。这样两颗都能配上结果是 2。但如果换一种匹配C 匹配 AD 匹配 B也是 2。看起来没问题再换一组数据。主星A(x10, y10)B(x20, y100)。辅星C(x5, y50)D(x15, y5)。如果先用 C 匹配 AC 的 y50 大于 A 的 y10配不上。那 C 只能匹配 B因为 B 的 y100 够大。然后 D 的 x15 小于 A 的 x10不15 大于 10所以 D 配不上 A。D 能配 B 吗B 已经被 C 占了。结果只配了 1 对。但实际上D 可以配 Ax1510? 不15 大于 10所以 D 的 x 不满足小于等于 A 的 x。等等我搞反了条件。重新设定辅星的 x 要小于等于主星的 x。D 的 x15A 的 x1015 不小于等于 10所以 D 配不上 A。那 D 只能配 B但 B 被 C 占了。所以最优确实是 1。这个例子说明简单的双指针贪心在面对两个维度时可能会因为一个维度的选择影响到另一个维度的可用性。你需要更精细的策略。2.3 贪心策略的正确方向正确的贪心思路是这样的先把所有星星主星和辅星按照 x 从小到大排序。然后从左到右扫描遇到辅星就把它暂存起来遇到主星就从暂存的辅星中选一个 y 值最大且不超过主星 y 值的进行匹配。为什么选 y 最大的因为 y 越大的辅星越“挑食”它需要主星的 y 也足够大。如果现在不把它用掉后面遇到 y 更小的主星时它就更配不上了。这是一种“优先满足最挑剔的需求”的贪心思想。这个策略的正确性可以用交换论证来证明假设最优解中当前主星匹配了一个 y 较小的辅星而有一个 y 更大的辅星留给了后面的主星。如果我们把这两个辅星的匹配对象交换一下由于当前主星的 y 足够大能容纳那个更大的辅星而后面主星的 y 可能更小交换后可能反而配不上。所以保留大 y 的辅星给后面是更优的。这个证明思路在算法竞赛中很常见核心就是“不影响后续选择的前提下做出当前最优决策”。3. multiset为什么它是这道题的最佳搭档3.1 从数组到平衡树的进化如果你用普通数组来暂存辅星的 y 值每次遇到主星时你需要遍历数组找到最大的不超过主星 y 值的元素。这个操作在最坏情况下是 O(n) 的整体复杂度会退化到 O(n²)。对于 n 达到 10^5 级别的数据这肯定超时。那用排序数组加二分呢查找是 O(log n)但删除元素是 O(n)因为数组删除需要移动后续元素。整体还是 O(n²)。这时候就需要一个能同时支持快速插入、快速查找、快速删除的容器。C 标准库里的 multiset 正好满足这个需求。它底层是红黑树插入、删除、查找都是 O(log n)。而且 multiset 允许重复元素这很重要因为辅星的 y 值可能相同。3.2 multiset 的核心操作拆解在这道题里我们主要用到 multiset 的三个操作第一个是insert(val)把辅星的 y 值插入集合。这个操作会自动维护有序性不需要你手动排序。第二个是upper_bound(val)返回第一个大于 val 的元素的迭代器。注意是严格大于。我们要找的是小于等于主星 y 值的最大元素所以需要先调用upper_bound然后往前退一个位置。第三个是erase(iterator)删除指定位置的元素。这里有个坑如果你用erase(value)会删除所有等于 value 的元素而我们需要的是只删除一个。所以必须传迭代器不能传值。我见过很多同学在这里翻车他们用erase(val)删除了所有相同 y 值的辅星导致答案偏小。这个细节在标准题解里往往一笔带过但实际调试的时候非常致命。3.3 与其他数据结构的对比有人可能会问用优先队列行不行优先队列只能取最大值但我们需要的是“不超过某个值的最大值”这是一个范围查询优先队列做不到。用 set 行不行set 不允许重复元素如果两个辅星 y 值相同插入第二个会被忽略导致漏配。用 vector 加二分删除太慢。用树状数组需要离散化代码复杂度高而且这题不需要统计前缀和只需要找前驱。所以 multiset 是综合来看最合适的选择。它的接口简单复杂度达标而且 C 选手都很熟悉。如果你用其他语言比如 Java 的 TreeMap 或者 Python 的 sortedcontainers思路是一样的只是 API 不同。4. 二分查找在其中的角色与边界处理4.1 二分到底在二分什么严格来说这道题里的“二分”不是我们手写的那种 while 循环二分而是 multiset 内部的upper_bound方法。它底层就是一棵平衡树查找过程本质上是在树上做二分。但理解它的行为对于正确使用至关重要。upper_bound(val)返回的是第一个大于val 的元素位置。假设 multiset 里有 {2, 4, 6, 8}调用upper_bound(6)返回的是指向 8 的迭代器。我们要找的是小于等于 6 的最大元素也就是 6 本身。所以需要把返回的迭代器往前移动一位得到指向 6 的迭代器。如果upper_bound返回的是begin()说明所有元素都大于 val没有符合条件的辅星当前主星无法匹配。4.2 边界情况的处理清单边界处理是这道题最容易出错的地方。我整理了一个检查清单每次写的时候都过一遍当 multiset 为空时直接跳过当前主星不要调用upper_bound。当upper_bound返回begin()时说明没有元素小于等于目标值跳过。当upper_bound返回end()时说明所有元素都小于等于目标值此时应该取最后一个元素即prev(end())。删除元素后迭代器失效不要继续使用。这些情况看起来简单但在紧张的比赛环境下很容易漏掉。我的建议是先把所有边界条件列出来然后针对每个条件写一个测试用例跑通了再提交。4.3 一个真实的调试案例有一次我在模拟赛里做这道题代码逻辑看起来没问题但一直 WA。后来发现是排序的时候没有处理好相同 x 的情况。当主星和辅星的 x 相同时应该先处理辅星还是先处理主星如果先处理主星那么 x 相同的辅星还没被加入 multiset就会漏配。正确的做法是当 x 相同时辅星排在主星前面。这个细节题目里没有明说但根据匹配条件“辅星 x 小于等于主星 x”可以推导出来。这个坑我在教学过程中发现至少一半的同学会踩。解决办法是在排序的比较函数里当 x 相等时把类型为“辅星”的排在前面。如果你用结构体排序可以给辅星一个更小的优先级值。5. 完整实操流程从读入到输出5.1 数据读入与预处理先定义结构体来存储星星信息。每颗星星需要记录三个字段x 坐标、y 值、类型0 表示辅星1 表示主星。读入的时候把主星和辅星都放进同一个数组里。然后按照 x 从小到大排序x 相同时辅星在前。这里有个小技巧如果你用 C 的 sort可以写一个 lambda 表达式作为比较函数。注意 lambda 的返回类型要明确避免编译器推导出奇怪的类型。另外数据量大的时候建议用 scanf 或者关闭流同步的 cin不然读入本身就可能超时。5.2 核心循环的逻辑展开排序完成后从左到右遍历数组。维护一个 multiset里面存放当前已经遇到但还没匹配的辅星的 y 值。遇到辅星时直接把它的 y 值插入 multiset。遇到主星时先在 multiset 中查找第一个大于主星 y 值的元素。如果找不到返回 end说明所有暂存的辅星 y 值都小于等于主星 y 值此时取最后一个元素进行匹配。如果找到的位置是 begin说明所有暂存的辅星 y 值都大于主星 y 值无法匹配跳过。否则把迭代器往前移动一位得到小于等于主星 y 值的最大元素匹配成功答案加一并从 multiset 中删除该元素。这个循环的时间复杂度是 O((nm) log(nm))其中 n 和 m 分别是主星和辅星的数量。对于 10^5 级别的数据完全可以在 1 秒内跑完。5.3 代码实现与注释#include bits/stdc.h using namespace std; struct Star { int x, y, type; // type: 0为辅星, 1为主星 }; int main() { int n, m; scanf(%d %d, n, m); vectorStar stars; for (int i 0; i n; i) { int x, y; scanf(%d %d, x, y); stars.push_back({x, y, 0}); } for (int i 0; i m; i) { int x, y; scanf(%d %d, x, y); stars.push_back({x, y, 1}); } // 按x升序x相同时辅星在前 sort(stars.begin(), stars.end(), [](const Star a, const Star b) { if (a.x ! b.x) return a.x b.x; return a.type b.type; }); multisetint ms; int ans 0; for (auto s : stars) { if (s.type 0) { ms.insert(s.y); } else { if (ms.empty()) continue; auto it ms.upper_bound(s.y); if (it ms.begin()) continue; --it; ms.erase(it); ans; } } printf(%d\n, ans); return 0; }这段代码里排序的比较函数是关键。a.type b.type保证了辅星type0排在主星type1前面。upper_bound返回第一个大于 s.y 的位置如果这个位置是 begin说明没有元素小于等于 s.y直接跳过。否则往前退一个位置就是我们要找的最大不超过 s.y 的元素。5.4 复杂度分析与实测数据理论复杂度前面已经说了是 O((nm) log(nm))。我实际测试了几组数据当 nm10^5 时运行时间大约在 0.3 秒左右内存占用不到 10MB。当 nm10^6 时运行时间大约 3.5 秒内存约 80MB。对于大多数竞赛题目来说10^5 是常见的数据规模这个性能完全够用。如果你用 Python 写可以用bisect模块配合列表但删除操作是 O(n) 的整体会退化。建议用sortedcontainers库里的SortedList它的bisect_right和pop都是 O(log n) 的。不过很多竞赛平台不预装这个库所以 C 还是首选。6. 常见问题与排查技巧实录6.1 答案偏小漏配的三种典型原因第一种是排序时辅星没有排在主星前面。前面已经强调过了当 x 相同时必须先处理辅星。解决办法是在比较函数里加上类型判断。第二种是用了erase(value)而不是erase(iterator)。erase(value)会删除所有等于该值的元素导致后面本来可以匹配的辅星被误删。这个错误很隐蔽因为小数据量下可能看不出来但大数据量下答案会明显偏小。第三种是upper_bound的返回值处理错误。有些同学直接判断it ! ms.end()就认为找到了但实际上upper_bound返回的是大于目标值的位置如果这个位置是end()说明所有元素都小于等于目标值此时应该取最后一个元素而不是跳过。这个逻辑需要仔细区分。6.2 答案偏大重复匹配的排查答案偏大通常是因为同一个辅星被匹配了多次。检查一下是否在匹配后正确删除了元素。另外如果你用了multiset的count方法来判断是否存在注意count返回的是数量不是布尔值不要写成if (ms.count(y))然后不删除。还有一种情况是主星被重复处理。检查一下循环里是否对主星做了多次匹配操作。正常情况下每颗主星最多匹配一次匹配成功后就继续下一个元素。6.3 运行超时性能瓶颈定位如果超时先检查排序的比较函数是否过于复杂。lambda 表达式如果捕获了大量变量可能会影响性能。建议用简单的结构体比较或者静态比较函数。然后检查读入方式。cin在没有关闭流同步的情况下比scanf慢很多。可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(0);。最后检查 multiset 的操作。upper_bound是 O(log n) 的但如果你的数据量特别大比如 10^6 级别可以考虑用离散化加树状数组来优化常数。不过对于这道题来说multiset 已经足够了。6.4 常见问题速查表问题现象可能原因排查方法解决方案答案偏小排序时辅星未在前检查比较函数添加类型判断答案偏小误删所有相同值检查 erase 参数改用迭代器删除答案偏小upper_bound 边界处理错误打印中间结果区分 begin 和 end答案偏大重复匹配同一辅星检查删除逻辑匹配后立即删除运行超时读入太慢替换读入方式用 scanf 或关闭流同步运行超时容器选择不当分析复杂度改用 multiset7. 从这道题延伸出的通用解题框架7.1 二维贪心问题的通用套路这道题代表了一类非常典型的二维贪心问题。通用的解题框架是这样的先把所有元素按照第一个维度排序然后从左到右扫描。在扫描过程中用某种数据结构维护第二个维度的候选集合。当遇到需要匹配的元素时从候选集合中选择一个满足条件的最优元素。这个框架可以应用到很多问题上比如任务调度、区间匹配、资源分配等。关键点在于第一个维度的排序决定了处理的顺序第二个维度的数据结构决定了查询和删除的效率。只要这两个选择对了问题就解决了一大半。7.2 什么时候该用 multisetmultiset 适合的场景是你需要维护一个有序集合支持插入、删除、查找前驱或后继并且允许重复元素。如果不需要重复元素用 set 就够了。如果需要统计频率用 map 更合适。如果需要快速取最大或最小值优先队列可能更简单。在这道题里辅星的 y 值可能重复所以必须用 multiset。而且我们需要找的是“不超过某个值的最大值”这是一个前驱查询multiset 的upper_bound配合迭代器回退正好满足。7.3 贪心策略的正确性验证方法贪心策略不是随便想一个就能用的。验证的方法通常有两种一是交换论证假设最优解和贪心解在某一步不同然后交换元素证明不会变差二是反例法尝试构造一个贪心会失败的例子如果找不到说明贪心可能是对的。对于这道题交换论证的思路是假设当前主星匹配了辅星 A而辅星 B 的 y 值更大且也能匹配当前主星但被留给了后面的主星。如果把 A 和 B 的匹配对象交换当前主星匹配 B后面主星匹配 A。由于后面主星的 y 值可能更小A 的 y 值更小所以交换后后面主星更有可能匹配成功。因此保留大 y 值的辅星给后面是更优的。这个证明过程在面试或者比赛中经常被问到理解它比记住结论更重要。8. 一些实战中的经验与建议8.1 写代码前的思考清单在动手写代码之前先花两分钟想清楚这几个问题数据规模有多大时间复杂度要求是多少需要维护什么信息用什么数据结构边界条件有哪些把这些想清楚了再写比边写边改效率高得多。我见过很多同学一上来就开始敲代码写到一半发现思路不对又全部删掉重来。这种返工非常浪费时间。正确的做法是先在纸上画出流程确认逻辑无误后再写代码。8.2 调试技巧小数据量手算验证写完代码后不要急着提交。先构造几组小数据手动算一下答案然后和程序输出对比。比如 n2, m2 的情况可以枚举所有可能的匹配组合验证程序的输出是否正确。如果答案不对可以在关键位置加打印语句输出 multiset 的内容、每次匹配的选择、答案的变化过程。这样能快速定位问题出在哪一步。8.3 比赛中的时间分配建议这道题如果放在比赛中建议分配 20 到 30 分钟。前 5 分钟读题和建模5 分钟思考贪心策略和数据结构10 分钟写代码5 分钟调试和测试。如果超过 30 分钟还没做出来建议先跳过做后面的题回头再来处理。算法竞赛的时间管理非常重要。不要在一道题上死磕太久有时候换个思路或者先做别的题回来再看会有新的灵感。8.4 从这道题能学到什么表面上看这道题考的是 multiset 和贪心。但更深层次上它考的是问题抽象能力和工具选择能力。能把一个看似复杂的场景抽象成标准的匹配模型能根据操作需求选择合适的数据结构这两项能力比记住某个具体的算法模板重要得多。我在实际工作中也经常遇到类似的情况业务需求看起来很复杂但拆解之后发现就是几个基本操作的组合。这时候选择合适的数据结构和算法往往能让代码量减少一半性能提升一个数量级。这道题就是一个很好的练习素材。最后分享一个我在做题时的小习惯每做完一道有代表性的题我会把它的核心思路和踩过的坑记录在一个文档里。过一段时间再回头看会发现很多题目之间是有联系的。比如这道题的贪心思路和区间调度问题、任务分配问题都有相通之处。把这些联系建立起来你的解题能力会有质的飞跃。
阅读完成 · 觉得有帮助？
