上周我在某在线评测系统上刷题碰见了一道让人又爱又恨的题PAT——The World‘s Richest题面后面还特意挂了一句“注意运行超时的问题”。题目本身读起来很简单给出一群人的姓名、年龄和净资产然后给出若干个年龄区间查询每次输出这个区间内净资产排名最靠前的几个人。可我第一版代码写完在最后一个大数据点上直接超时整个提交栏弹红心态瞬间就崩了。后来静下来复盘才发现这道题真正的考点不是“会不会排序”而是“能不能把多次查询变成一个可复用的结构”。这篇就把我从 TLE 到 AC 的完整过程写出来包括第一版为什么慢、优化思路是怎么来的、完整代码长什么样以及几个很容易踩进去的细节坑。如果你也在刷类似的“多查询榜单题”这篇文章应该能帮你省下很多调试时间。1. 这道“世界首富”题到底在考什么1.1 原题核心多查询榜单输出任务先还原一下题目场景。输入的第一行是两个整数 N 和 MN 是名单里的总人数M 是查询次数。接下来 N 行每行给出一个人的名字、年龄、净资产再接下来 M 行每行给出一个年龄区间 [A, B] 和一个数字 K要求输出年龄在 A 到 B 之间、净资产排名前 K 的个人。输出时有明确的排序规则净资产从大到小排如果两个人的净资产相同名字字典序小的排前面。如果某个查询在年龄区间内没有符合条件的人就输出一行 None。常见的数据规模大概是 N 和 M 都到 10 万的级别年龄范围在 1 到 200 之间K 一般限制在 10 以内。这个题我最初以为就是个“排序应用题”但仔细一想会发现困难点很明确M 是 10 万级别每次都把年龄区间内的人捞出来重新排序复杂度完全不可控。题目真正考的是预处理怎么让每次查询不用重复排序直接用已经准备好的有序结构快速选出前 K 个人。1.2 为什么一看就会、一写就超时很多第一次做这道题的人包括我脑子里浮现的操作都是同一个模板每次读取一个查询 [A, B] 和 K。遍历所有人把年龄在 A 到 B 之间的人放进一个临时数组。对这个临时数组按“资产降序、姓名升序”排序。输出前 K 个或者输出 None。听起来行云流水甚至觉得很简单。但在 N10 万、M10 万 的情况下这个方案最坏会做什么事呢每次查询都有可能把 10 万人全部放进临时数组然后做一次 O(N log N) 的排序。10 万次查询每次对 10 万人排序这个操作量不是线性增长是乘数级别的。哪怕排序本身很快在严格的时间限制下也必然是超时的重灾区。所以这道题给我们的第一课是题目里真正的大头不是“排序”而是“查询次数太多导致重复排序”。如果只做一次全局排序然后想办法把查询变成轻量操作思路就对了。2. 第一版“暴力实现”的超时复盘2.1 朴素思路与代码我第一版代码长这样可能很多读者也会写出类似的东西#include bits/stdc.h using namespace std; struct Person { string name; int age; int worth; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorPerson people(n); for (int i 0; i n; i) { cin people[i].name people[i].age people[i].worth; } auto cmp [](const Person a, const Person b) { if (a.worth ! b.worth) return a.worth b.worth; return a.name b.name; }; while (m--) { int a, b, k; cin a b k; vectorPerson tmp; for (int i 0; i n; i) { if (people[i].age a people[i].age b) { tmp.push_back(people[i]); } } sort(tmp.begin(), tmp.end(), cmp); if (tmp.empty()) { cout None\n; continue; } // 按 k 输出 int cnt 0; for (auto p : tmp) { cout p.name p.age p.worth \n; cnt; if (cnt k) break; } } return 0; }这段代码的逻辑没有错误甚至在小数据样例上跑得飞快。我当时心想N10 万又如何排序一次也就几十毫秒10 万次排序顶多多等一会儿嘛。但实际情况完全不是这样。2.2 复杂度拆解与耗时瓶颈一次查询最坏要遍历 N 个元素然后对 N 个元素排序。排序复杂度大约是 O(N log N)。C 里的 sort 在 10 万数据量下一次大约要执行 100 多万次比较这个单次开销不大。但问题是 M 也是 10 万整体最坏就是 10 万 × 100 多万次比较也就是 1000 亿级别的比较量。哪怕实际数据没有让每次查询都覆盖全量年龄只要平均一次查询涉及几万人整体也会落在几十亿次操作量。这个量级在任何常规在线评测系统里都不可能通过。我一开始还抱着“也许评测数据没那么毒”的侥幸心理结果最后一个点超时。查了运行时间暴力版本在前几个小数据点上没问题越往后耗时增长越离谱。也可以说这个题就是故意用大数据来筛选会做预处理的人。3. 从“每次都排序”到“一次全局排序年龄分桶”3.1 关键洞察前K答案只可能来自全局最富的人回到问题本身。我们不需要知道每个年龄区间里的完整排序只需要输出前 K 个。K 很小一般不超过 10。那么一个自然的问题是有没有可能把那些“永远不会进入任何查询前 10”的人提前扔掉举个简单例子假设同一个年龄桶里已经有 10 个人他们的财富都比第 11 个人高。那么无论查询怎么设置只要查询包含这个年龄并且只输出前 10 名那第 11 个人永远没有机会被输出。因为在他之前至少 10 个同龄人已经满足了“年龄相同且财富比他高”的条件他最多只能排在这个年龄桶的第 11 位。这个逻辑是整道题的突破口。如果我们先把所有人按“资产降序、姓名升序”做一次全局排序然后按年龄放进桶里每个年龄桶内部自然也是有序的。接下来只要把每个年龄桶的多余人口截断桶里留下的人就是真实查询中可能被输出的人。3.2 年龄桶截断保留多少个才安全既然 K 最大是 10那么理论上每个年龄桶留下前 10 个人就够了。但实际写代码时我会选择留下前 100 个原因很简单这个题只输出前 10 名保留前 100 绝对不会漏答案同时数据量也不会因此爆炸。为什么说保留 10 已经足够因为在同一桶内如果一个人排在桶内第 11 名那么在他前面至少已经有 10 个同龄人财富不比他少并且这 10 个人只要年龄范围包含该年龄就会天然排在查询结果的前 10 位之外。这个人不可能挤进前 10。那为什么还要保留 100主要是心理学和鲁棒性因素。有时候我记不清题目里 K 的上限或者懒得反复检查边界条件。保留 100 并不会让复杂度变劣因为年龄范围 1 到 200最多 200 个桶每个桶 100 人也就是 2 万人。查询阶段如果用“多指针”而不是真的把这 2 万人重新排序开销依然很小。3.3 查询阶段多指针扫描 vs 每次重新排序有了经过排序和截断的年龄桶之后我们面临一个新的选择每次查询时是把年龄区间内的所有桶合并起来重新排序还是用更聪明的办法重新排序听起来简单但危险很大。假设年龄区间跨度是 100每个桶平均留下 100 人一次查询就要排序 1 万人再乘上 10 万次查询又回到了不可接受的数量级。更合理的做法是多指针扫描。我们给每个年龄桶配备一个指针初始都指向桶首。每次从年龄区间内所有桶的当前指针中挑出“全局序排在最前面”的那个人输出他然后把对应桶的指针向后移动一位。重复执行 K 次直到输出足够数量或者所有指针都已越界。因为每个桶内部已经有序所以这些指针指向的人就是每个桶当前最强的人。每次只要把年龄区间内若干个桶的“当前最强”放在一起比较选出来的就是全局当前最强。这种做法的好处是每次查询最多只需要比较 K 轮每轮比较 200 个桶也就是大约 200 × 10 2000 次比较和 N 完全无关。这个量级即使在 10 万次查询下也能轻松承受。4. 完整实现与关键代码说明4.1 结构体定义与全局排序下面是我优化后提交通过的 C 版本。先定义 Person 结构体#include bits/stdc.h using namespace std; struct Person { string name; int age; int worth; };排序比较器要严格遵循题目的规则bool cmp(const Person a, const Person b) { if (a.worth ! b.worth) return a.worth b.worth; return a.name b.name; }这里有一个细节有并列财富时按姓名升序排序比较器必须写成而不是。这样能给所有人一个严格的全序关系避免 sort 因为比较器不严格而出现未定义行为。4.2 预处理落桶与截断主函数里读入 N、M 和所有人之后直接对全局数组排序然后按年龄分配到桶里int n, m; cin n m; vectorPerson people(n); for (int i 0; i n; i) { cin people[i].name people[i].age people[i].worth; } sort(people.begin(), people.end(), cmp); const int MAX_AGE 200; const int TOP_LIMIT 100; vectorvectorPerson bucket(MAX_AGE 1); for (auto p : people) { if ((int)bucket[p.age].size() TOP_LIMIT) { bucket[p.age].push_back(p); } }因为全局排序已经完成所以在落桶时直接保留每个年龄桶前 100 个人即可。很多人喜欢在 sort 之后截断原理一样。这个预处理的总复杂度是 O(N log N)一次性开销完全可控。4.3 查询多指针线性扫描取前K查询部分是整道题的核心。我用了两个数组一个记录每个桶的当前指针位置另一个记录每个桶是否还有剩余候选人vectorint ptr(MAX_AGE 1, 0); while (m--) { int a, b, k; cin a b k; // 每次查询都要重置指针只重置范围内的桶 for (int age a; age b; age) { ptr[age] 0; } vectorPerson ans; while ((int)ans.size() k) { int bestAge -1; for (int age a; age b; age) { if (ptr[age] (int)bucket[age].size()) continue; if (bestAge -1) { bestAge age; continue; } Person cur bucket[age][ptr[age]]; Person best bucket[bestAge][ptr[bestAge]]; if (cmp(cur, best)) { bestAge age; } } if (bestAge -1) { break; } ans.push_back(bucket[bestAge][ptr[bestAge]]); ptr[bestAge]; } if (ans.empty()) { cout None\n; } else { for (auto p : ans) { cout p.name p.age p.worth \n; } } }这段查询逻辑有三个容易写错的地方我一一踩过放在这里提醒当前指针不能越界。在比较cur和best之前必须确认ptr[age] bucket[age].size()否则读到空数据会崩溃。每次查询前要重置指针。如果不重置第二次查询时会从上一次结束的位置开始答案必然错误。因为年龄区间可能不同上一轮推出的桶首指针毫无意义。用cmp(cur, best)判断谁更优。这里的cmp是全局排序比较器放在查询里天然保证输出顺序和题目要求一致。我自己第一版优化代码在这里犯了一个蠢错把指针重置放在了读a,b,k之前导致第一次查询后指针全部乱掉最后结果错得莫名其妙。调试了很久才发现是这个低级问题。4.4 输入输出与常数优化优化完核心算法还想再挤一点运行时间。N 和 M 都是 10 万级别输入输出如果处理不好也会成为超时的帮凶。我第一版用了cin和cout再加上ios::sync_with_stdio(false)在数据量不算极端时能用。但到了这道题我更推荐直接用scanf和printf或者用string的printf配合固定格式输出printf(%s %d %d\n, p.name.c_str(), p.age, p.worth);另外一个减少输出 I/O 的小技巧把每个查询的输出放到一个ostringstream里最后一起打印或者直接用printf按行输出也足够。我的提交版本就是直接用printf通过没问题。5. 实测效果与进一步提速5.1 同数据下三种版本对比我专门在自己本地上造了一组接近极限的数据N100000M100000年龄分布均匀K 随机取 1 到 10。三种版本的表现如下版本核心复杂度实测结果暴力筛选 每次排序O(M × N log N)严重超时最后一个点无法通过全局排序 年龄桶前100 查询时重新排序收集O(M × 200 × 100 log(...))仍然很慢偶尔能过但风险大全局排序 年龄桶截断 多指针扫描O(N log N M × K × 年龄跨度)通过运行时间大幅下降我最终提交的版本在本地数据上跑完大约只需要原来暴力版本的几十分之一时间。原因就是每个查询的最大比较次数被压到了 2000 次左右而不是一次排序几万人。5.2 可选的进阶优化多指针扫描已经很稳但如果遇到时间限制更严格的平台还可以再往前一步把“每次扫描每个桶的当前指针”改成“优先队列”。思路是每次查询时先把年龄区间内所有非空桶的当前元素放进一个小顶堆或大顶堆堆顶就是当前最优。然后每弹出一个元素就把该元素所在桶的指针向后移动一位并把下一人放入堆中。这样每次查询的复杂度大约是 (桶数 K) × log(桶数)比线性扫描多一个 log但常数可能更小。对于这道题线性扫描已经足够优先队列版本更适合 K 或者年龄跨度更大的变体题。还有一个小优化是提前剪枝如果年龄区间内所有桶剩余元素总数都不超过 K可以直接把桶首的若干元素全部输出不用做 K 轮比较。但这种优化对总复杂度的影响不大代码却会复杂一些所以我最终没采用。6. 复盘这道题教我的三件事6.1 先看数据范围再写代码这道题最让我印象深刻的不是解法本身而是我一开始完全没有把“10 万次查询”当成一个真实的规模。写第一版的时候脑子里只有样例数据下意识觉得“既然需要排序那就排序吧”却忘了排序的调用次数会被 M 放大到不可接受。现在养成一个习惯拿到题目先看数据范围在心里估算一遍最坏复杂度。如果发现某个操作会被查询次数反复触发就一定要思考能不能通过预处理分摊成本。6.2 “取前K”先把数据变小很多榜单类问题的共同特征都是“只输出前 K 个”而 K 通常很小。只要 K 很小就可以大胆对数据做截断丢掉那些不可能进入答案的人。这不是投机取巧而是充分利用了问题约束。就像这道题里每个年龄桶只需要保留前 10 或前 100 个人查询阶段就不会被大数据量拖垮。下次遇到“查询区间 取前 K”的题可以先冷静问自己一句是不是所有数据都要保留答案多半是否定的。6.3 超时的根因排查顺序一旦遇到超时我现在的排查顺序是固定的先看 IO有没有用scanf/printf有没有关闭同步。再确认是不是把本该只做一次的排序放进了循环里。最后才看有没有办法用更高效的数据结构。这道题两个坑都占了输入输出用的 cin查询里还在反复 sort。把这两个改掉之后代码的通过率立刻上升。对我来说这道题就是一次很好的“刷题思维矫正”——它没考什么冷门算法却反复地让你理解自己要处理的数据规模到底是什么量级。从那之后我再看到题目备注里的“注意运行超时的问题”都会先敬畏起来。