其实一场模拟赛打完最让人睡不着的不是没做出来的压轴题而是那种一眼看上去“好像有点思路、再想想又晕了”的题。C1168《热血格斗场》对我来说就是这种题。当时卡了大概半小时交了一版错的赛后花了一整个晚上去补把从读题到正解的整条链路捋清楚了。这篇文章就把我的完整思考过程写出来包括走了哪些弯路、为什么错、正解是什么、代码怎么落地希望对同样在这道题上栽过跟头的同学有点帮助。1. 这道题到底在问什么题面还原与隐藏条件先说结论C1168是一个典型的“动态集合查询前驱后继”问题外壳是格斗场内核其实是数据结构。很多同学看到“格斗”“战斗力”“编号”这些词第一反应是排序、贪心、模拟实际上题面里藏了一个非常关键的条件稍不注意就会把问题想复杂。1.1 核心机制战力相近者先行题面的设定大致是这样有一个格斗场里面可以不断加入新的格斗者。每个人有两个属性一个是出场编号可以理解成加入的顺序一个是战斗力数值。每当一个新格斗者进入格斗场系统会在他加入的那一刻从已经存在的格斗者中选出一个人进行比赛。选择的标准是找战斗力与新人最接近的已有格斗者。这里要仔细抠“最接近”这三个字。不是找比自己强的也不是找比自己弱的而是找差值的绝对值最小的那一个。如果存在两个候选者一个战斗力比新人高一点一个比新人低一点且差值相同这个时候就要看编号取编号较小的那个也有的版本规定是取战斗力差值最小若两个方向差值相同则取战斗力较小的那个具体要以原题为准。这个设定有一个隐含的坑它要求你在任意时刻都能快速知道“所有已存在格斗者中谁的战斗力离当前新人最近”。换句话说这本质上是一个动态集合的最近邻查询问题。你需要支持两种操作插入一个元素带编号、带战斗力查询一个元素在集合中的前驱和后继。1.2 为什么说这题不是排序能解决的有人在赛场上第一反应是把所有格斗者按战斗力排个序然后每次新来一个人的时候二分找位置不就行了吗听起来很合理但问题在于格斗者是一个一个加入的你不可能等所有人都到齐了再排序。每加入一个人都要基于“当前已经加入的人”来选对手而不是基于最终所有人。这就意味着如果你用静态排序的思路每次插入后都要重新维护有序性。最直白的做法是每来一个人就重新排一次序复杂度直接炸掉。假设有10万个格斗者最坏情况下是O(n^2 log n)的复杂度满数据规模下结果可想而知。所以这道题给你的信号非常明确不能在“排序”上做文章必须在“动态维护有序结构”上想办法。这也就是为什么我一开始走了弯路——我没有第一时间把它理解成“动态集合”而是试图用一堆离线技巧去绕结果把自己绕晕了。2. 第一次尝试我从“前缀最值”想到的偏科解法先交代一下我最初的想法因为这也是补题报告里最有价值的一部分把我当时是怎么想的、为什么这么想、最后为什么翻车完整还原出来。2.1 为什么我会想到前缀最值那套东西看到“战斗力接近”我第一反应是离线处理。既然要从已有的人里找最接近的那我是不是可以把所有人的加入顺序当成一个时间轴维护一个“到目前为止战斗力最大值/最小值”之类的东西假如能证明最佳匹配一定来自当前战斗力最大或最小的人那问题就变成了两个极值查询可以直接用前缀最值数组做掉。我当时是这么推的新人的战斗力如果是x那老选手里有的人战斗力比他大有的人比他小。最接近的应该要么是“目前所有比他大的人里最小的那个”要么是“目前所有比他小的人里最大的那个”。从感觉上看这似乎只需要维护两个信息比我大的最小值、比我小的最大值。这个思路的问题在于“比他大的人里最小的那个”并不等于“全局最大值”也不等于“某个前缀最值”。它需要你在一个动态集合上做“条件最值查询”而这个“条件”本身是和新人战斗力x挂钩的。你不可能只维护一两个全局量除非你能证明匹配永远发生在全局最大或全局最小的人身上。2.2 我构造的反例全局极值与局部最优脱节为了验证这个想法我赛后自己构造了一组数据。假设目前场上已经有三个人编号A战斗力10、编号B战斗力50、编号C战斗力1000。现在新人战斗力为60。按照“前缀最值匹配极值”的路子新人只会考虑当前最大1000或某种极值但显然它最应该匹配的是B战斗力50因为B与它的差距是10而A与它差50C与它差940。B既不是全局最大也不是全局最小它是一个“夹在中间”的元素。这就说明我那个思路的本质缺陷最近邻查询的结果往往藏在集合的“中间区域”而不是两端。你不可能绕开对整个有序集合的访问只靠极值去确定答案。除非你维护的是一棵完整的平衡树否则根本无法回答“介于某个区间内的元素是谁”这个问题。2.3 为什么暴力set遍历也不可取还有一个比前缀最值更朴素的想法用红黑树存所有元素每次新人来的时候暴力遍历整棵树找最接近的。这个想法的正确性没问题但是复杂度完全没救。红黑树虽然能保证log n级别的插入和删除但如果你每次都从头到尾遍历一次查询就是O(n)整体还是O(n^2)。所以问题的核心其实不是“有没有数据结构”而是“能不能在树结构上利用有序性做前驱后继查询”。如果你知道红黑树支持lower_bound和upper_bound那你自然会想到用std::set。但如果你只是把红黑树当成一个能自动排序的容器每次遍历拿答案那跟暴力没区别。我当时就没第一时间意识到“有序集合自带前驱后继查询”这个能力反而去搞了一堆奇怪的维护量。补题之后我最大的体会是看到“动态集合查询接近值”第一反应应该直接跳到“平衡树前驱后继”不要绕弯。3. 正解核心平衡树维护有序战力集合这道题的正解其实非常干净。你需要维护一个“战斗力有序集合”并且每个元素额外带上一个编号。每当新格斗者加入你就在集合里找它的前驱和后继按题面规则选出最匹配的输出对手编号然后把新人插入集合。3.1 前驱与后继最近邻查询的本质拆解所谓前驱就是集合中“严格小于新人战斗力”的最大元素后继就是“严格大于新人战斗力”的最小元素。如果集合里存在和新人战斗力相同的元素处理方式要看题面约定。有的题设规定战斗力互不相同那就很简单不存在等于的情况。如果可能存在相同战斗力那“最接近”的判定就要小心很多选手在这里被卡。接续之前说的一旦你有了前驱和后继你要做的就比较操作了。设新人战斗力为x前驱的战斗力为pre后继的战斗力为nxt。那么需要比较x - pre和nxt - x哪个更小。如果前者小选前驱如果后者小选后继。如果一样大按编号来决定。这个比较逻辑不复杂但一定要在写代码前想清楚不要等到代码写完了再回来补判等逻辑那样容易漏。3.2 为什么std::set够用但multiset要多想一层在C里标准库的std::set是一个红黑树实现的有序集合底层天然支持O(log n)的插入、删除和查找。最关键的是它自带lower_bound和upper_bound这两个接口可以在树上游走快速找到第一个不小于某个值的元素以及第一个大于某个值的元素。用这两个接口前驱和后继都能在O(log n)时间内得到。有一点需要特别留意如果你用std::set默认它是去重的。如果题面允许战斗力相同那你必须要手动处理“相同战斗力”的情况。处理方式通常有两种一是存pair战斗力, 编号利用pair的字典序让相同战斗力但编号不同的元素都能存进去二是直接用std::multiset允许重复元素然后每次查询的时候配合lower_bound和upper_bound来定位。我第一次实现的时候用了multiset结果在遍历的时候被相同战斗力的元素搞得心态有点崩。因为multiset里如果有多个相同战斗力lower_bound返回的那个迭代器不一定对应编号最小的那个你得额外在代码里做判断。后来我干脆把“战斗力编号”打包成pair塞进std::set因为编号互不相同pair整体就不可能重复了直接去重特性反而帮了忙。3.3 匹配规则的边界先比战力差再比编号这是很多人会忽略的细节。题面在“最接近”这件事上如果两个方向和新人差值的绝对值一样大应该选谁假设新人战斗力为60前驱战斗力为58后继战斗力为62两者差值都是2。这个时候就不能再看战斗力了必须比编号。编号较小的获胜因为系统认定编号小的老格斗者“更有资格”接受挑战。有人在实现的时候把这个顺序搞反了先比编号再比战力差。这就不对了规则说的是“最接近”是第一优先级的编号只是平局决胜。如果前驱战斗力是58后继是10000战斗力差那边显然应该选58跟编号没关系。只有差值一样的时候才轮到编号出场。我补题的时候在这个地方wa了一发原因是判断条件写得不够清醒。后来我把逻辑整理成一段独立函数输入前驱、后继和新人内部先判差值再判编号最后返回择优之后的那个老格斗者编号。这样代码结构一目了然也不会因为主流程里判断太多而出错。3.4 哨兵节点边界条件的老朋友写平衡树查询的时候边界条件是很难绕开的一道坎。当你查前驱的时候万一新人战斗力比当前集合里所有元素都小那前驱不存在查后继的时候万一新人战斗力比所有元素都大那后继也不存在。如果你直接用迭代器去做判断代码会变成一堆“if迭代器是不是begin()”“if迭代器是不是end()”的嵌套。我一般在比赛里会直接塞哨兵。具体做法是在集合里初始化的时候就加入一个战斗力为无穷大(INT_MAX)和无穷小(INT_MIN)的元素或者用long long的极大极小值。这样无论新人是什么战斗力前驱和后继都一定存在。查询的时候只需要正常取迭代器然后判断一下取到的到底是不是哨兵避免把哨兵当成真实格斗者输出。这个哨兵技巧对很多平衡树/有序容器题都通用属于那种“省心省力、以空间换逻辑清晰度”的小套路。不过要注意哨兵元素的编号一定要设置成不可能出现的值否则可能在比较编号时被误伤。比如哨兵编号设成0而真实格斗者编号从1开始这样就不会冲突。4. 代码落地与细节处理从理想到能过编译思路理清楚之后写代码其实很快。但“快”不等于“一次就过”。我在实现过程中踩了几个非常细微的坑包括pair排序规则的理解、迭代器的隐式转换、以及赶时间的时候容易犯的复制粘贴错误。4.1 结构体与比较函数的选型我推荐直接用C的std::setstd::pairlong long, int来写。为什么用pair因为pair自带完整的比较逻辑先比first再比second完全不需要自定义结构体或仿函数。战斗力放进first编号放进second。好处是当你用lower_bound找后继的时候可以直接传入一个make_pair(战斗力, -1)之类的东西让它在相同战斗力的情况下简直接跳过编号较小的位置找前驱的时候用upper_bound配合make_pair(战斗力, INT_MAX)可以定位到某个位置前一个。这里很多人容易懵的是为什么lower_bound和upper_bound的搭配能精准定位。我自己的理解方式是lower_bound返回的是第一个“大于等于”目标的元素如果目标pair的second设成一个很小的数那么在相同战斗力的情况下它会从上界开始找避免误将编号较小的相同战斗力元素当后继。upper_bound返回的是第一个“大于”目标的元素如果目标pair的second设成一个很大的数那它会跳过所有相同战斗力的元素落在比当前战斗力大的第一个元素位置这时候取它的前一个迭代器就是前驱。用pair还有一个好处就是当两个候选者战斗力差值一样时想比编号可以直接比较pair.second不必从结构体里再取一次字段。4.2 核心代码插入与查询的完整流程下面是我补题时亲手写并通过本地验证的核心逻辑使用的环境是C17。代码里我用long long存战斗力避免某些测试数据在加法或差值计算时溢出int范围。#include bits/stdc.h using namespace std; const long long INF (1LL 60); setpairlong long, int S; int main() { int n; scanf(%d, n); // 哨兵保证前驱后继查询永远有结果 S.insert({-INF, 0}); S.insert({INF, 0}); for (int i 1; i n; i) { long long power; scanf(%lld, power); if (S.size() 2) { // 当前只有哨兵说明这是第一个人 // 题面规则第一个人进入时无人与其匹配 S.insert({power, i}); continue; } // 寻找后继第一个当前战斗力的真实元素 auto it_ge S.lower_bound({power, -1}); // 寻找前驱最后一个当前战斗力的真实元素 auto it_le prev(S.upper_bound({power, INT_MAX})); int ans_id -1; long long best_gap LLONG_MAX; // 注意it_ge和it_le都有可能是哨兵 // 但因为我们插入了INF和-INF哨兵所以必然不是end()或begin()前的空位 if (it_ge ! S.end()) { long long gap llabs(it_ge-first - power); if (gap best_gap) { best_gap gap; ans_id it_ge-second; } else if (gap best_gap it_ge-second ans_id) { ans_id it_ge-second; } } if (it_le ! S.begin()) { long long gap llabs(it_le-first - power); if (gap best_gap) { best_gap gap; ans_id it_le-second; } else if (gap best_gap it_le-second ans_id) { ans_id it_le-second; } } printf(%d\n, ans_id); S.insert({power, i}); } return 0; }这段代码我尽量写得直白没有做什么花哨的优化。它的核心就是lower_bound和upper_bound两个查询然后比较两个候选者。可能有人会问如果集合里已经存在和新人战斗力相同的元素怎么办我的定位方式决定了它会找到那个相同的战斗力元素因为pair中可以靠second来控制选择。如果你希望相同战斗力之间优先匹配编号小的那在ans_id赋值时的相等判断会起作用。4.3 这版代码里我踩过的三个细节坑第一个坑出在哨兵的输出上。第一次写的时候我没有检查it_ge或it_le是否指向哨兵结果新人来的时候把哨兵当成了老格斗者输出输出了一个0号选手。这个错误在数据量小的时候根本发现不了因为小数据里很可能恰好不会出现查询失败的情况一上大数据输出结果里冒出0就说明哨兵被当成真实选手了。解决办法很简单要么在初始化的时候规定真实编号从1开始哨兵编号为0输出时如果ans_id为0就说明选到了哨兵但更稳妥的办法是干脆在比较前排除哨兵。我最终选择的是第二种明确判断it_ge ! S.end()和it_le ! S.begin()同时哨兵编号为0时如果选中了哨兵gap可能会异常地大不会成为最优解。第二个坑是prev(S.upper_bound(...))这个操作。有人会问为什么要用upper_bound而不是lower_bound来找前驱因为前驱的定义是“严格小于”当前战斗力的最大元素。lower_bound的第一反应会找到“大于等于”当前战斗力的元素那就不满足“严格小于”了。所以必须用upper_bound先找到第一个严格大于当前战斗力的位置再往前挪一格才能保证落在小于等于的范畴内。如果你忘了往前挪一格会将当前这个人自己当成前驱逻辑就完全错了。第三个坑是差值计算时用了llabs。如果战斗力范围很大直接用int的abs会有溢出风险。我测试的时候故意构造了一组大数就是要确认不会在求绝对值这个地方挂掉。正常情况下如果战斗力范围在int内int abs也能过但既然要用long long存就老老实实用llabs不要嫌麻烦。4.4 复杂度分析与数据规模预判使用std::set之后每次插入是O(log n)每次查询前驱后继也是O(log n)。总复杂度就是O(n log n)。在10万级别甚至20万级别的数据下这个复杂度是稳过的运行时间通常在零点几秒到1秒之间取决于常数和评测机器。如果你用暴力遍历或者每次重新排序就是O(n^2)或者O(n^2 log n)在数据量稍大的时候基本等于TLE。还有一个小细节如果你用scanf/printf而不是cin/coutIO开销会小很多。因为数据量大时IO可能会成为隐形瓶颈。如果你坚持用cin/cout请务必加上ios::sync_with_stdio(false); cin.tie(0);否则有些题目真的会因为IO太慢而超时。5. 评测结果对比与失误复盘这25分钟亏在哪写完代码之后我在本地用随机数据和自己构造的边界数据各测了几轮最后才提交。虽然最终通过了但比赛时的那25分钟浪费得非常可惜。复盘下来问题不是出在不会写set而是出在“没在正确的时间想到正确的方法”。5.1 我当时为什么花了25分钟才定位到数据结构现在回头想我很清楚自己当时卡在哪了。我在第一眼看到“战斗力接近”的时候满脑子都在想“怎么用一个简单的前缀信息维护出答案”甚至想到了离线查询、排序后处理这些路径。这种思维惯性来自前面几道题都是排序、贪心、区间的专题我的脑子被前面的题带跑了。如果我能从一开始就提醒自己“这是动态插入查询最近邻”我应该会立刻想到平衡树和前驱后继。可是问题在于动态插入这件事在题面里太自然了以至于我没有把它当成一个“关键信号”来对待。我总以为用一个数组就能模拟插入然后在数组上做二分查找。实际上数组的插入是O(n)的二分只能加速查找不能加速插入。这是补题报告里最值得写下来的一笔看到“动态集合”四个字脑海里应该立刻弹出候选数据结构列表——平衡树、跳表、哈希表、线段树、树状数组然后逐个检查哪种能同时支持插入和有序查询。而不要先默认“数组排序”够用等到超时了再回头换。5.2 边界数据自测清单我的压测方法为了让代码更有把握我赛后用了几组自测数据来验证第一组是只有一个人。此时不需要输出匹配对象只需要把这个人插入集合即可。假如你代码在这里崩了那说明没有正确处理“空集合”的情况。第二组是战斗力相同的人。假设第一个人战斗力100第二个人战斗力100第三个人战斗力100。这三个人的匹配规则会因为编号产生差异。我用这组数据确认了代码在“相同战斗力”下的行为没有越界。第三组是极值的组合。比如新人战斗力是全场最小或者全场最大。这种时候哨兵就发挥作用了。如果你没有插哨兵会发现代码里需要单独判断前后继是否存在稍不注意就数组越界或者迭代器失效。我的哨兵方案在这里帮了大忙。第四组是随机大数据。我生成了10万条随机数据与暴力程序对拍。暴力程序就是每来一个人就遍历一遍现有集合找最近邻虽然复杂度高但正确答案是不会变的。对拍跑了好几轮确认随机情况下我的程序输出和暴力一致。5.3 从这道题里我能带入其他题目的通用经验说真的C1168这道题本身并不算难数据结构也不高级。但它带给我的不是“会写set”这么简单的收获。它让我重新审视了自己的解题流程是先思考性质再匹配工具还是先猜测工具再去套题面。道理想得很好必须先确认“这是个动态有序集合查询问题”再去想set、平衡树这些东西。反过来一上来就想着要不要用平衡树容易被数据结构带偏方向。比如有一类题表面上也是动态插入、查询最近点但如果点不是一维的战斗力而是二维平面坐标那std::set就无能为力了。你可能会需要平衡树套堆、KD树之类的更重的东西。但如果是一维的那set完全够用。所以关键还是“识别问题的维度”而不是直接背模板。5.4 如果战斗力可以重复怎么做最小改动我在比赛时假设了战斗力互不相同但如果原题没有明确说明稳妥起见要按可重复来考虑。实际上我在网上翻过这道题的讨论确实有路过的同学问“如果战士战斗力一样怎么办”。我的建议是别用单纯的std::setlong long改为std::setstd::pairlong long, int让相同战斗力但不同编号的元素成为pair意义下的不同元素。这样做的代价是查询前驱和后继的逻辑会变得稍微复杂一丢丢因为你有时需要跳过某个信战斗力元素里的特定编号。比如你想找前驱用了--upper_bound({power, INT_MAX})它会直接跳过所有战斗力等于power的元素落在严格小于power的位置这就是真正的“严格前驱”。如果想找“不大于power的最后一个人”那可以用--lower_bound({power, 0})。前者和后者在战斗等时有明显区别。写之前一定要想清楚题面到底要的是“严格小于”还是“小于等于”不要想当然。6. 一句真话set不是万能的想清楚问题和工具的匹配才是这道题补完之后我在代码旁边留了一行注释“动态集合最近邻查询std::set足够但前提是别用错查询方式。”这句话看起来平平无奇却是我比赛中真正付出代价换来的。如果你也被卡在类似题目上我建议你按这个顺序去自查第一步明确题面是动态插入还是静态排序第二步明确匹配优先级是只比差值还是差值编号第三步明确是否存在相同战斗力第四步再动手写代码。顺序对了这套题就是一道送分的数据结构练习题。最后再分享一个我自己的小习惯补题报告写完以后我会把“为什么会想歪”单独写一段记录而不是只贴一份AC代码。因为代码一个月后可能就忘了但你当时想歪的原因往往能提醒你下次避开同样的坑。C1168的想歪原因我已经写在这儿了希望你不用亲自交那25分钟的学费。