Atcoder Beginner Contest 448 的 C 题被不少刷题群戏称为“STL 好题”。原因很简单它把两种最常见的 STL 容器——std::map 和 std::priority_queue——塞进了同一道题里让你发现同一个操作居然能有两种完全不同的模拟方式。我做这道题的时候第一反应是 map 从低到高进位写完只用了十几行后来看群里讨论才发现用最小堆从最小的两个数开始合并逻辑更贴近题目文字描述。两种写法各有各的爽点也各有各的坑。如果你正在备战 AtCoder Beginner Contest、蓝桥杯、ICPC 这类需要快速上手的比赛这道题值得花半小时认真拆一遍。题目本身不长但很能考你对容器语义的理解。很多初学者在学 STL 的时候只会背每个容器的 API遇到真实问题根本不知道挑哪个容器。这道题就是很好的“容器选型训练场”同一种合并逻辑既能用有序键值表解决也能用最小堆解决而且两种做法的思考路径完全不一样。我尽量把推导过程、完整代码、踩坑记录都写清楚你看完可以直接把代码搬走跟着样例过一遍。1. 题目拆解合并同类项看看题目到底想考你什么1.1 还原后的题意描述我先把题目转成人话。给定一个长度为 N 的整数序列每个数字看作一张牌。你可以重复执行下面的操作任意次选择两张数值完全相同的牌比如两张 x把它们拿走换成一张 x1 的新牌。目标是合理安排合并顺序问最终这张“牌桌”上能够出现的最大数字是多少。形式化描述就是输入第一行一个整数 N第二行 N 个整数 A_1, A_2, ..., A_N。操作规则是 x x - x1需要消耗两张数值为 x 的牌产生一张数值为 x1 的牌。多次操作后输出最终多重集合中元素的最大值。输入范围我按 ABC 常见的设置来写1 ≤ N ≤ 2×10^51 ≤ A_i ≤ 10^9。这个数量级意味着 O(N log N) 的算法完全可行O(N^2) 的暴力模拟铁定超时所以必须借助合适的数据结构。为了讲解方便我把样例固定成下面这三个版本后面所有推导都围绕它们展开。样例 13 1 1 2输出3。样例 24 1 1 1 1输出3。样例 33 1 2 3输出3。这三个样例非常典型前两个说明合并会出现“连击”效果第三个则提醒你当无法合并时答案就是原序列里的最大值。题面看着简单但真正写代码的时候边界情况比想象中多得多这正是 STL 容器发挥作用的地方。1.2 样例手推从具体操作体会“连击”和“孤立”先把三个样例的合并过程完整走一遍体会一下操作的节奏。样例 1初始牌面是[1, 1, 2]。先合并两张 1得到一张 2桌上变成[2, 2]。这里的 2 出现了两次一个是原来就有的另一个是刚合并出来的于是又可以合并一次得到一张 3。最终桌上只剩一张 3答案就是 3。样例 2初始牌面是[1, 1, 1, 1]。第一次合并两张 1得到 2桌上变成[1, 1, 2]第二次再合并剩下的两张 1又得到一张 2桌上变成[2, 2]第三次合并两张 2得到 3。答案 3。注意这里“连击”的关键每次合并产生的新牌有可能和桌上已有的同数值牌再次配对所以整个过程不是简单做一轮就结束而是要一直持续到“能合并的都合并完”为止。样例 3初始牌面是[1, 2, 3]。没有任何两张牌数值相同所以一次操作都做不了最终最大数字就是原来的最大值 3。手推完就发现这个操作其实很像“进位制”。两张 1 可以换一张 2两张 2 可以换一张 3两张 3 可以换一张 4……如果把每个数字 x 看成第 x 位的筹码那么每两个低一级筹码就可以兑换一个高一级筹码。整个问题就等价于给你一堆筹码兑换到不能再兑换之后最高能换到哪一级。1.3 建模思维把“合并”看成“进位制”“进位制”这个视角非常重要它直接导出了第一种思路。你可以把每个数值的出现次数看作一个计数器从最小的数开始每次遇到数值 x 出现 cnt 次就把 cnt/2 向上进位给 x1如果 cnt 是奇数还会剩下一张孤立的 x。这个过程和十进制加法中的“逢十进一”差不多只不过这里是“逢二进一”。举个例子如果输入是[1, 1, 1, 1]计数结果是 1 出现 4 次。处理 1 的时候4/2 2所以向上位贡献两张 2处理 2 的时候当前 2 的总数是 22/2 1所以向上位贡献一张 3。最终答案就是 3。用代码实现这个“从低位到高位进位”的过程最顺手的容器就是 std::map因为它能按数值从小到大存储每个数的出现次数天然符合进位方向。另一条思考路径是贪心永远盯着当前最小的两张牌。如果它们相同就合并如果它们不同那么更小的那一张永远找不到第二个同伙注定只能作为“孤立数字”留在桌上。这个视角非常直白模拟时需要一个能快速取出最小数字、同时支持动态插入新数字的容器std::priority_queue最小堆就是最合适的选择。到这里两种思路的数学基础都清楚了。下面先聊容器选型再分别看两种实现。2. STL 选型分析为什么 map 和 priority_queue 是这道题的最佳主角2.1 std::map 的特点与适用场景std::map 是 C STL 里的有序键值对容器底层是一棵红黑树。它的三个核心特性对这道题特别重要第一内部按键的大小升序排列。这意味着我们可以用迭代器从最小键一路走到最大键正好对应“从小到大处理数字”的进位逻辑。第二增删查操作的时间复杂度都是 O(log N)在 N 不超过 2×10^5 的场景下非常从容。第三operator[] 有一个很“危险”也很方便的行为如果键不存在它会自动创建该键并初始化为默认值然后返回引用。利用这个特性mp[num 1] c / 2;这一行就能完成“向上进位”不需要先判断键是否存在。但正如后文要讲的这个特性如果用不好也会带来死循环的坑。什么场景选 map答案很明确当你需要按键的顺序做处理或者需要频繁查询某个键当前是否存在、计数是多少的时候。本题“从最小数字开始进位”的需求简直就是为 map 量身定做的。反过来如果用 unordered_map虽然单次查询平均 O(1)但它是无序的无法保证从小到大的处理顺序进位逻辑就很难写了。2.2 std::priority_queue 的特点与适用场景priority_queue 是容器适配器底层默认用 vector 实现一个二叉堆。它只支持三个主要操作push 插入、pop 删除堆顶、top 访问堆顶元素。默认情况下它是一个大根堆也就是堆顶是最大元素如果要变成最小堆必须写出完整类型priority_queuelong long, vectorlong long, greaterlong long pq;中间那个 vector 是底层容器参数非常容易漏掉漏掉就无法编译。很多新手第一次写小根堆都被这里卡住所以我会在常见问题里专门提。什么时候选 priority_queue当你的算法只关心“当前全局最小或最大元素”不需要遍历所有元素也不需要按键值索引。本题思路二里每次都要取当前最小的两个数字做处理合并完又要重新插入堆中这就是堆的经典使用场景。堆的插入和删除堆顶都是 O(log N)整个算法的总复杂度依然很稳。2.3 两种容器如何匹配题目需求为了更直观地对比我把两个容器在这道题里的角色整理成一张表对比维度std::mapstd::priority_queue底层结构红黑树二叉堆是否有序按键升序只有堆顶有序核心操作迭代器遍历、operator[] 插入/查询push、pop、top时间复杂度查询、插入均为 O(log N)插入、删除堆顶 O(log N)适合处理方向从小到大遍历所有数字反复取当前最小的一小撮数字本题的角色计数并向上进位模拟合并与丢弃过程看这张表就能感受到两者不是谁替代谁的关系而是两道完全不同的思考路径。map 强调的是“全局有序遍历”priority_queue 强调的是“动态取极值”。这道题同时用到两种思想所以被叫做“STL 好题”确实有道理。3. 思路一std::map 从低到高完成“进位合并”3.1 核心思想按数值从小到大处理能向上进位就进位思路一的本质是模拟进位。先把所有数字读进 map键是数字值是出现次数。然后从最小的键开始遍历对每个当前数字 num如果它出现的次数 c 小于 2说明它无法向上进位最多只能作为孤立数字留在桌上。如果 c 大于等于 2那么每两张 num 可以合成一张 num1也就是把 c/2 加到 num1 的计数上。无论是否进位num 这一位已经处理完了因为即使留下奇数个 num它们也不可能再和更小的数字发生关系了。最后当迭代器走到 map 的最后一个键时这个键就是最终桌面上出现的最大数字。为什么不是中间某个“更大的合并结果”因为如果某个数字 x 还能继续向上进位那么 x1 这个键一定会被插入 map且会被迭代器遍历到如果某个更大的数字没有出现说明没有足够的牌能合成它。所以 map 最后一个非零计数的键就是答案。3.2 C17 完整代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; maplong long, long long cnt; for (int i 0; i N; i) { long long x; cin x; cnt[x]; } long long ans 0; for (auto it cnt.begin(); it ! cnt.end(); it) { long long num it-first; long long c it-second; // 当前数值至少要能达到ans 先记录一下 ans num; // 只有数量 2 才向上进位否则不插入新的键 if (c 2) { cnt[num 1] c / 2; } } cout ans \n; return 0; }这段代码放在 AtCoder 的 C20 环境下可以直接提交输出完全符合题意。3.3 逐段解析边界分支、迭代器安全、防死循环代码很短但每一行都有讲究我按顺序说。先看类型。我把键和值都设成了 long long而不是 int。题目里 A_i 上限是 10^9合并后最大数字可能达到 10^9 log2(N)也就是大约 10^9 18用 int 其实也能放下但竞赛中宁可多占一点空间也不要去赌边界long long 更稳妥。再看cnt[x]这段读入。利用 map 的 operator[]如果 x 不存在就自动创建为 0再自增变成 1如果存在就直接自增。这是 map 最方便的用法也是 STL 新手最应该熟悉的操作之一。然后是主循环。这里有个非常关键的细节我们在遍历 map 的同时往 map 里插入了新的键num 1。很多选手看到这种代码会害怕迭代器失效。好消息是std::map 的插入操作不会让任何已有的迭代器失效因为红黑树的节点是独立分配的插入新节点不会移动老节点。而且由于num 1一定大于num新插入的键一定在当前迭代器之后所以it之后一定会遍历到它不会出现“漏处理”或“无限循环”的问题。这是 map 相对 vector、deque 这类顺序容器最大的优势之一。当然前提是你要给插入加一个if (c 2)的保护。如果不加假设 c 是 1你也会执行cnt[num 1] 0这等于强行插入一个值为 0 的新键。map 里出现一个计数为 0 的键循环还会继续处理它处理它时又会插入下一个值为 0 的键……整个程序就会陷入死循环直到内存耗尽。这是我实际写这道题时踩过的最大的坑后面我会在常见问题里细说。关于 ans 的更新我把它放在循环体最前面每次都等于当前 num。这样即使当前数字 c 2它作为孤立数字的“候选答案”也会被记录。最后循环结束时ans 自然就是 map 中最后一个被遍历到的键。3.4 复杂度与正确性证明要点时间复杂度很好分析一共有 N 个初始元素每个元素进入 map 一次。map 上的插入、查询都是 O(log N)。进位过程中每次“合并”都会让元素总数减少至少 1所以最多产生 N 级向上进位整个循环的处理次数是 O(N)。总复杂度 O(N log N)。空间复杂度是 O(N)map 中最多存下 N 个不同的键。正确性可以从两个角度确认。一是前面说的进位制从最小位一路进位上去每一个 num 的计数在处理时已经包含了所有低位传上来的贡献所以不会漏。二是反证法如果最终答案是 K那么 map 中一定会出现键 K 且计数非零如果 map 中还出现比 K 更大的键说明 K 不是最大值矛盾。所以最后一个非零键就是正确答案。4. 思路二std::priority_queue 用最小堆模拟“贪心合并”4.1 核心思想每次只处理最小两个元素处理不了的直接记录答案思路二换了一个视角不再全局计数而是把每个数字直接丢进一个最小堆然后一次次处理。每一步从堆里取出两个最小的数字 a 和 ba ≤ b分两种情况如果 a b说明这两个数字可以合并把 a1 放回堆中。因为合并后的新数字可能还能和别的数字继续合并。如果 a b说明堆里没有第二个 a 能和它合并了。a 是整个堆里最小的数字如果它都找不到同伙那比它更大的数字更不可能来和它配对。所以 a 注定是最终桌面上的孤立元素我们把 a 记为候选答案然后把 b 放回堆中等待后续处理。这个过程一直持续到堆里只剩一个数字它自然也是孤立元素或堆为空。每次循环至少会减少一个数字所以循环次数不超过 N算法一定终止。这里有一个很容易踩的直觉陷阱为什么不能从大的数字开始合并因为大的数字即使孤立也大概率是答案但如果一开始就把大数字合并掉了可能会破坏小的数字配对的机会。我举个反例输入[1, 1, 2]正确合并是先合成两个 1 得到 2再把两个 2 合成 3但如果从大往小合并第一次取 2 和 1两个不同只能丢弃 1剩下的牌变成[1, 1]两个 1 合成 2最终答案最多是 2错过正确答案 3。所以这道题只能从小往大贪心priority_queue 必须配成最小堆。4.2 C17 完整代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; priority_queuelong long, vectorlong long, greaterlong long pq; for (int i 0; i N; i) { long long x; cin x; pq.push(x); } long long ans 0; while (!pq.empty()) { if (pq.size() 1) { ans max(ans, pq.top()); pq.pop(); break; } long long a pq.top(); pq.pop(); long long b pq.top(); pq.pop(); if (a b) { pq.push(a 1); } else { ans max(ans, a); pq.push(b); } } cout ans \n; return 0; }同样可以直接提交和思路一代码风格完全一致都采用万能头文件和快速 IO。4.3 逐段解析堆操作细节与歧义分支先看小根堆的声明priority_queuelong long, vectorlong long, greaterlong long pq;priority_queue 模板有三个参数元素类型、底层容器类型、比较器。默认比较器是 less也就是大根堆改成 greater 后变成小根堆。你可能会问为什么不能像set那样直接写priority_queuelong long, greaterlong long这是因为 priority_queue 作为容器适配器必须显式给出底层容器类型这是 C 标准的规定。记住这个格式就好经常写就能背下来。读入部分很简单每个数字直接 push。堆中允许重复元素这正是 multiset 和堆共有的特性也是我们需要的两张相同的 1 要能同时被取出。主循环里我用了pq.size() 1作为出口判断然后取堆顶更新答案。有人可能更习惯用while (pq.size() 1)然后在循环外再处理剩下那个元素。两种写法都能过但我个人更喜欢在循环内判断这样代码更紧凑也避免了循环结束之后还要再访问一次堆顶的空指针风险。else 分支里我把较小的 a 记录为候选答案然后把较大的 b 放回堆中。这里有一个很容易忽略的细节b 可能还能和后面的某个数字合并。比如[1, 2, 2, 3]的某一步中b 是 2后续如果又出现一个 2这两个 2 就应该合并成 3。所以必须把 b 放回去否则会漏掉合并不可能的答案。4.4 两种方法对比与选型指南写到这里两种思路的代码都齐了。我来做一个综合对比方便你在赛场上快速判断该选哪一种。对比维度思路一map 进位法思路二priority_queue 合并法思维模型计数排序 进位制贪心模拟当前最小两个数代码量更短主循环逻辑简单稍长分支判断多一点易错点循环内插入新键0 值键导致死循环小根堆写法取完要放回 b处理方向从小到大遍历所有数字反复取全局最小两个直观程度偏数学需要理解进位贴近题目操作容易用样例手推时间复杂度O(N log N)O(N log N)空间复杂度O(N)O(N)适合谁喜欢建模、追求极致代码简洁刚学完堆、想巩固贪心思想我的个人建议是如果你是第一次见这道题而且对堆比较熟建议优先写思路二因为它的每一步都对应题目描述中的操作错误原因容易通过样例找出来。如果你已经熟练掌握了 map 的迭代器语义思路一能写得更快代码也更短在分秒必争的 ABC 或 ICPC 中很有优势。两种思路都实现一遍才是最好的学习方式。5. 实战踩坑记录与 STL 使用技巧5.1 我在写这两个版本时踩过的坑先说思路一最大的坑在 map 遍历中无脑插入新键。我第一次写的时候偷懒没有加if (c 2)保护结果本地跑1这个输入程序直接卡死。原因前面已经分析过operator[] 会为不存在的键创建默认值 0而 c 为 0 时又会继续创建下一个更大的键无穷无尽。解决方法是加一层判断或者写成if (c / 2 0) { cnt[num 1] c / 2; }这两种写法等价但我更推荐if (c 2)读起来更直观。再说思路二的两个坑。第一忘记把 priority_queue 改成最小堆。我用默认的大根堆写了一次样例 1 就直接输出 2花了五分钟才反应过来。第二在 a ! b 的情况下没有把 b 放回堆里。这个错误更隐蔽它不会导致样例错但在某些数据下会漏掉合并机会最终答案偏小。这两种错误都属于“看起来代码对了但逻辑差一步”只有通过构造边界用例才能发现。还有一个通用坑int 溢出。A_i 最大能到 10^9合并次数多的时候答案能到 10^9 N 级别用 int 虽然勉强放得下但在更严格的题目里可能直接爆炸。我在这道题里统一用 long long省心。5.2 边界用例测试清单写竞赛代码最重要的就是构造边界用例。我常用下面这一组来验证这道题1 5答案应为 5。只有一张牌无法合并。2 1 1答案应为 2。两个 1 合成一个 2。3 1 1 1答案应为 2。两个 1 合成 2还剩一个孤立 1最大是 2。5 1 1 1 1 1答案应为 3。四个 1 合成两个 2两个 2 合成一个 3还剩一个孤立 1。4 1 1 2 2答案应为 3。两个 1 合成 2此时三个 2 中拿两个合成 3剩一个孤立 2。5 1 1 2 2 2答案应为 4。两个 1 合成 2此时有四个 2两两合成为两个 3再合成为一个 4。3 1 2 3答案应为 3。完全无法合并。把这些用例在两个代码上各跑一遍全部通过基本就稳了。如果某一种思路输出和另一种不一致说明其中一边的边界逻辑有 bug优先检查“孤立元素有没有正确记录”。5.3 竞赛中 STL 使用的几点长期经验这道题除了“题解”本身还有一个更长期的启发STL 容器不是背下来的是用会的。第一要理解容器底层的行为差异。同样是“插入新元素”map 不会让已有迭代器失效unordered_map 在 rehash 时可能让迭代器失效vector 在扩容时会让所有迭代器失效。如果你不清楚这些规则在循环里一边遍历一边插入就会写出难以排查的 bug。建议遇到这类问题第一时间查阅 cppreference 上关于“iterator invalidation”的说明而不是凭感觉猜。第二学会用“容器特性”反推算法。看到“需要按键顺序处理”优先想到 map / set看到“需要反复取最小最大值”优先想到堆看到“需要快速判断某个元素是否存在”优先想到 unordered_set / unordered_map。这道题正好同时训练了前两种直觉。第三比赛时千万不要为了追求“最标准”而手写红黑树或手写堆。STL 的实现经过充分优化性能足够满足竞赛需求而且内部细节比如红黑树的旋转、堆的调整都已经帮你处理好了。你把节省下来的时间用来构造边界数据性价比高得多。第四提交前一定要检查数据类型和读入速度。ios::sync_with_stdio(false);和cin.tie(nullptr);这两行我几乎每道题都写它能显著加快 cin / cout 的速度。如果再配合long long类型至少能避开一半的卡时间和溢出问题。我个人在实际练习中的体会是这道题真正有价值的不是“AC”本身而是通过它把 map 和 priority_queue 的适用场景彻底想明白了。第一遍写思路一你学会了进位建模第二遍写思路二你巩固了贪心模拟。之后遇到类似的“合并相同元素”问题无论题目怎么变形你都能在几秒钟内选出合适的容器。最后再分享一个小技巧当两种思路都能做出同一道题时建议把复杂度、代码量、易错点一起对比着看这种“一题多解”的训练方式对竞赛思维提升远比盲目刷十道新题更有效。后面如果时间充裕我还可以沿着这个思路把“multiset / map / 堆的选择问题”再整理一期把同类型题目做个合集。
