PAT The World‘s Richest：从暴力超时到分桶多路归并的Top K优化实战-北京尧图网络

最近刷题碰到一道名字很吓人的题PAT——The Worlds Richest题面开头还专门标了一行小字“注意运行超时的问题”。这个名字翻译过来就是“世界上最富有的人”听起来像财经新闻实际是一道很典型的算法题给你一群人的年龄和资产再给你一堆查询每个查询指定一个年龄区间要求输出这个区间里资产最高的前K个人。题目本身不绕真正坑人的就是那行小字——几乎每个人交上去的第一版解法都会栽在超时上。这道题适合谁来练正在备编程能力考试的、准备算法面试的、或者单纯想练一练“怎么把一个暴力思路改成能跑过的方案”的人。它考的不是什么偏门数据结构而是最常用的排序、扫描、IO优化和复杂度估算含金量相当高。下面我把我的解题过程和踩坑记录完整写出来从暴力解到满分解从C到Python一次性聊透。1. 先弄懂题目在说什么1.1 输入输出与答案规则题目描述大致是这样给出N个富豪的信息每个富豪有三个字段姓名不超过8个字符、年龄、净资产。之后有M次查询每次查询给出三个参数K、年龄下限Amin、年龄上限Amax。要求输出年龄在[Amin, Amax]内的富豪中净资产排名前K的人。注意排序规则有三层先比净资产大的在前净资产一样比年龄小的在前再一样按姓名字典序。我习惯先用一个微型样例把规则钉死。假设Alice 30岁 1000万Bob 25岁 1000万Charlie 40岁 500万Dave 30岁 900万Eva 25岁 800万查询是K2年龄区间[28,40]。落在区间内的人有Alice、Charlie、Dave按财富排是Alice 1000、Dave 900、Charlie 500所以输出前两名就是Alice和Dave。Bob虽然也是1000万但年龄25不在区间里直接排除。这时候你对排序规则应该没有任何疑问了规则是全序的财富权重最高年龄和名字只是并列时的裁决条件。输出格式上这类题一般要求每个查询占若干行一行一个人区间内没人时输出一个None。看起来很简单对吧问题全藏在数据范围后面。1.2 数据范围里的杀气N可以到10^5M可以到10^3K最多100年龄范围一般不超过200。这个数量级意味着什么先记住一句话复杂度超过10^8次简单操作在C上就开始危险超过10^7Python基本要跪。暴力做法是每次查询遍历N个人筛选出区间内的然后排序输出。算一下复杂度M次查询每次排序是O(N logN)总比较次数大约是10^5 × 10^3 × 17 ≈ 17亿次。就算评测机每秒能跑10^9次简单比较这也是将近两秒起步再算上IO和排序常数超时是必然的。Python如果用内置sortC语言实现的排序本身挺快但外层扫描和数据处理也会卡得厉害。这里我要专门纠正一个常见误解很多人觉得“我K很小所以排序时排K个就行”。这是错的你先要筛出区间内所有的富豪才知道前K名是谁而筛选本身要扫全表。不改变整体思路只在排序环节小修小补解决不了根本问题。2. 暴力解法为什么必挂2.1 最直观但最致命的写法新手拿到题目第一版代码一般长这样伪代码for each query (K, amin, amax): tmp [] for each person: if amin person.age amax: tmp.append(person) sort tmp by (worth desc, age asc, name asc) if tmp empty: print None else: print first min(K, len(tmp)) persons这个逻辑完全正确示例数据稳过。但直接交上去等待你的大概率是评测页面上的“运行超时”。问题出在两个地方一是tmp反复扩容、插入、排序每次查询都在构造新容器二是每次查询都得重新扫描N个人完全没有复用任何中间结果。也有人在上面做“优化”先按年龄把所有人分组每次查询只遍历区间内年龄对应的组而不是遍历全部N个人。这个方向是对的但效果很有限。年龄范围如果只有0到200而查询区间跨190个年龄那和扫全表几乎没有区别只有区间特别窄时才有明显提升。2.2 把1.7×10^9次操作拆开看复杂度账要一步步算。假设N100000M1000暴力方案每次查询的耗时来自两部分扫描加排序。扫描是O(N)排序如果区间内人数接近N每次就是O(N logN)。于是总比较次数大约是1000 × 100000 × 17约17亿这还是下限没算排序时的交换、字符串比较、构建临时容器的开销。C的std::sort比较函数如果内部还要比较std::string的字典序常数会更大。实际跑起来暴力解在常见评测环境中往往是2到5秒。常见的超时限制是1秒或2秒所以它连抢救的空间都没有。Python更惨即使你用read()批量读入把IO优化到极致17亿次Python层的操作也是不可能完成的耗时按分钟算。所以这里有一条铁律做算法题先看N和M的上限把复杂度写出来再动手。哪怕代码逻辑再漂亮复杂度不达标就是0分。这道题的题面特意提示“注意运行超时”其实就是出题人在提醒别一上来就暴力。3. 正解一次全局排序查询时数够K个就停3.1 核心观察现在说正解。题目的特殊点在于每个查询都要求“区间内前K名”而K≤100。假如已经按照“财富降序、年龄升序、名字字典序”把N个人排好了一遍那么每次查询时沿着这个全局有序数组从头扫到尾所有年龄落在区间的富豪天然就是该区间的正确排名。道理很简单截取一个有序序列的子集子集的相对顺序不变。于是查询变成从头扫描全局数组遇到年龄符合的人就输出每输出一个人计一个数一旦计满K就立刻停止。如果整张表扫完都不足K个说明区间内总共就没那么多人全部输出。如果一个人都没碰到输出None。这个方案为什么能躲过超时因为大多数查询在扫描很短的前缀时就能凑满K个人。比如K100而财富榜前100人里通常有不少人落在常见年龄区间扫几十个到几百个就结束了只有极少数查询需要多走一截这部分就是这道题的脏数据点下一章专门讲。3.2 为什么提前停不会影响正确性这里值得多说两句因为面试官经常会追问“凭什么只数K个就对”。我们把全局排序后的数组记作p[1]到p[N]其中p[1]是规则意义下的第一名。对一次查询年龄区间是A我们要求的其实是集合S {i | p[i].age ∈ A}中按规则排名前K个元素。因为规则是固定的全序关系S内部元素的相对顺序和它们在全局数组中的顺序完全一致。扫描时我们遇到的第r个属于S的人是p[i1]、p[i2]、…、p[ir]而且下标i1 i2 … ir所以p[i1]就是S中的第一名p[i2]是第二名以此类推。输出前K个正是S中的前K名。这个论证在K大于|S|时依然成立我们只是扫完整个数组然后自然退出并没有多输出一个人。所以“提前break”不会改变输出内容只会节省时间。这是整个截断优化的合法性基础。3.3 C参考实现直接放一份可跑的C代码。我用关闭同步的cin/cout不用fstream不用endl。#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; if (a.age ! b.age) return a.age b.age; return a.name b.name; } 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; } sort(people.begin(), people.end(), cmp); while (M--) { int K, amin, amax; cin K amin amax; int cnt 0; for (const auto p : people) { if (p.age amin p.age amax) { cout p.name p.age p.worth \n; if (cnt K) break; } } if (cnt 0) cout None\n; } return 0; }这里有个容易被忽略的点如果区间内人数不足K需要把区间内符合条件的人全部输出。上面代码天然处理了——扫完整个数组自然退出。但很多人会在这个分支犯错比如先统计一遍区间人数再决定要不要输出None结果白白多扫一次全表又把自己推到超时边缘。3.4 Python参考实现Python如果按常规方式写十个有九个会超时。我推荐的做法是用sys.stdin.buffer.read()一次性读入全部字节split()成列表排序用一个元组key(-worth, age, name)最后把每行输出装进列表join之后一次性write出去。import sys def main(): data sys.stdin.buffer.read().split() idx 0 n int(data[idx]); idx 1 m int(data[idx]); idx 1 people [] for _ in range(n): name data[idx].decode(); idx 1 age int(data[idx]); idx 1 worth int(data[idx]); idx 1 people.append((-worth, age, name)) people.sort(keylambda x: (x[0], x[1], x[2])) out_lines [] for _ in range(m): k int(data[idx]); idx 1 amin int(data[idx]); idx 1 amax int(data[idx]); idx 1 cnt 0 for neg_worth, age, name in people: if amin age amax: out_lines.append(f{name} {age} {-neg_worth}) cnt 1 if cnt k: break if cnt 0: out_lines.append(None) sys.stdout.write(\n.join(out_lines)) if __name__ __main__: main()注意几个细节负worth是为了让Python sort的默认升序变成财富降序age直接升序符合规则name字典序Python默认的字符串比较就是。输出这里我把每条富豪信息带上了年龄和财富值实际输出格式以题目为准有些版本只要求名字有些要求三个字段都打。我按三字段版本写读者自己改一行就行。这一版在全随机数据下通常能跑进两三秒但还不够稳。接下来聊为什么要继续优化以及众多题解刻意绕开的最坏情况。4. 更稳的加强版按年龄分桶加多路归并取Top K4.1 提前截断也有翻车的时候全局排序加提前截断能过绝大多数官方数据但它有一个隐藏软肋如果查询区间内富豪总数不足K扫描就必须走到数组末尾才能结束。比如某次查询K100但年龄区间里总共只有两个人那这次查询的代价就是O(N)如果M次查询全是这种“区间人很少”的类型总复杂度瞬间退回O(M·N)10^8级别。C勉强能打Python就非常悬。出题人如果想卡掉大量靠“提前break”混分的代码最有效的办法就是构造一堆冷门年龄区间的查询。我在一套对抗数据下实测Python的截断版跑了3秒多而同一份数据下面要说的分桶多路归并版只用1秒左右。这个差距就是“能稳定AC”和“看数据脸色”之间的区别。4.2 分桶思想年龄范围很小通常不超过200。我们可以在读入所有人之后按年龄分成最多200个桶每个桶内部按全局规则排序也就是财富降序、年龄升序、名字字典序。于是每个桶都是自身的有序序列。对于一次查询所有符合条件的富豪就是区间内各年龄桶的并集并且每个桶内部已经有序。现在问题变成如何从若干条有序链中按“财富优先”的原则拿出前K个经典做法是多路归并用一个最大堆堆顶始终是当前所有桶头部元素中规则序最靠前的一个每弹出一个就把同桶的下一个元素补进堆。重复K次或者堆空为止。因为K≤100桶的个数≤200每次查询的复杂度是O(K log A A)不再依赖N。这才叫稳定。有人问为什么不用A路数组每次遍历找最大值那样是O(A·K)A200、K100时每次查询2万次操作M1000就是两千万也能过。但堆写法更优雅而且能在面试里多聊几句。多路归并用堆的复杂度做到了O(K log A)堆内操作次数少常数也低。4.3 加强版核心代码先给出C桶的建法const int MAX_AGE 205; vectorvectorPerson bucket(MAX_AGE); for (auto p : people) bucket[p.age].push_back(p); for (int a 0; a MAX_AGE; a) { sort(bucket[a].begin(), bucket[a].end(), cmp); }然后查询时用优先队列。堆里每个元素需要知道三件事来源桶、桶内位置、实际人物。我用一个小结构体把它们包起来struct Node { int age; int pos; Person person; }; struct NodeCmp { bool operator()(const Node x, const Node y) const { return !cmp(x.person, y.person); } };查询逻辑是这样把区间内每个非空桶的第0个元素入堆循环最多K次每次弹出堆顶Node它就是当前区间内剩下的最靠前的富豪输出person然后把这个桶里的下一个元素bucket[age][pos1]补进堆。如果堆为空直接break。最后如果计数为0打印None。while (M--) { int K, amin, amax; cin K amin amax; priority_queueNode, vectorNode, NodeCmp pq; for (int a amin; a amax; a) { if (!bucket[a].empty()) { pq.push({a, 0, bucket[a][0]}); } } int cnt 0; while (!pq.empty() cnt K) { Node cur pq.top(); pq.pop(); cout cur.person.name cur.person.age cur.person.worth \n; cnt; int nextPos cur.pos 1; if (nextPos (int)bucket[cur.age].size()) { pq.push({cur.age, nextPos, bucket[cur.age][nextPos]}); } } if (cnt 0) cout None\n; }这个方案的代价是什么桶内排序总开销仍然是O(N logN)但查询段从O(N)变成了O(K log 200)在M很大时优势极其明显。代码量比截断版多大约二十行换来的是对任何输入都有确定性的复杂度。我在复盘的时候发现一个规律官方数据往往设计成截断版能过但自己构造对抗数据时一定要专门造“区间人少且K大”的用例。如果希望水平再上一层直接写多路归并版省得数据一换就翻车。4.4 输入输出与常数优化补充无论用哪种解法IO优化都是超时题的命门。C代码开头写ios::sync_with_stdio(false); cin.tie(nullptr);输出用\n而不是endl。这一句就能把大输入下的耗时砍掉接近一半。名字是字符串读入时用string没问题但如果习惯用scanf要先声明char name[16]再格式化读入最后构造string。别贪省事在结构体里塞固定数组。Python除了read()批量读入不要在循环里反复调用print。攒成list最后一次性join输出这是收益最大且最容易被忽略的优化。还有一个冷门点C排序比较函数里如果每次比较都通过const引用拿实参避免拷贝临时string值能省掉不少无谓的开销。5. 实测记录与排坑速查5.1 三组对抗数据实测我在一台普通开发机上做了三组实验不是评测环境只看相对趋势数据A小样例5个人3个查询验证正确性。数据B随机最大规模N100000M1000年龄均匀分布K100区间宽度40。数据C卡截断数据N100000M1000查询区间固定到只存在两个人的冷门年龄段K100。结果大致如下单位秒不同机器差异很大不用当作标准答案方案数据B数据C暴力C超时(2s)超时(2s)截断版C0.180.62分桶多路归并C0.220.25截断版Python0.953.24分桶多路归并Python1.101.16最值得看的是趋势截断版在数据C上耗时翻了近四倍多路归并版几乎不动。所以我的建议是只是应付常见评测截断版足够想把这道题彻底吃透直接上多路归并版顺便把优先队列的用法练扎实。5.2 六个高频坑位速查表坑位现象原因解决办法大输入卡IO小数据正常大数据超时cin默认和scanf同步导致慢加 ios::sync_with_stdio(false)区间无人输出空白或多输出None没区分“区间无人”和“人不够K”用一个计数器扫描结束仍为0就输出None排序规则错输出顺序和样例对不上财富同值没有继续比年龄和名字三层比较全写上别只写一层比较函数缺等值sort抛异常或内存错误C严格弱序要求等价时返回false每个字段相等时继续比下一字段最终返回falsePython逐行打印大数据全卡在输出print调用次数太多join后write一次截断版被卡冷门区间查询多每次都要扫全表分桶加多路归并5.3 一套排查超时的标准流程以后碰到任何一道题超时可以按我的顺序排查不敢说百发百中至少能救回大多数情况。第一步回头读数据范围把复杂度式子写出来对比10^8这个经验阈值。如果有多个循环嵌套找出瓶颈在哪。第二步用二分法定位在代码里给几个大段加计时分别测读入、排序、查询、输出看时间花在哪。很多人的超时其实是输出太慢不是算法问题。第三步构造对抗数据别只拿随机数据测。专门造最坏情况比如这道题里的冷门年龄区间看你的提前break是不是真的提前。第四步检查运行环境C开O2Python换解释器有时也有奇效。有时候你会发现超时和逻辑错误是两回事。先保证小数据完全正确再上大数据测性能别一上来就在超时里改逻辑容易把自己绕晕。这道题刷完我最大的感受是标题里那句“注意运行超时的问题”不是玩笑它直接决定了大多数人第一版的命运。我也写过暴力版交上去被超时打回来之后才静下心算复杂度再一步步从截断优化做到分桶多路归并。后来做其他Top K类题目时顺手就用上了这套“预处理加多路归并”的思路比如在数据流里维护频率Top K、在区间统计里取前若干名效率都很稳。最后再分享一个小技巧题目越像“简单排序”越要警惕数据规模凡是K很小又反复查询的场景优先想怎么把排序结果缓存下来而不是每次现排。把这个意识练成本能比多背几道模板题管用多了。

PAT The World‘s Richest：从暴力超时到分桶多路归并的Top K优化实战

相关推荐

低代码+条码/RFID：中小仓库物料追踪落地指南

AI大模型应用场景落地策略：从Demo到生产环境的实战指南

无人机追踪无人车：自适应卡尔曼滤波的MATLAB实现与调参实践

更多资讯

Ingress Nginx 高性能调优：从内核参数到 10 万 QPS 的完整实践

dart_scope鸿蒙适配实战：作用域驱动Flutter依赖生命周期治理

扩散语言模型技术全解析：并行生成、可控性与工程实践

YOLO11双模态改进源码解析：红外与RGB特征融合的目标检测实践

Ray 分布式对象溢出调优：应对千万级长上下文的跨存储治理

基于Python的网络小说分析系统：爬虫、文本挖掘与可视化实战

今日更新

智能硬件视频会议集成：从芯片选型到场景落地的全栈实践

FFmpeg音视频处理与5路RTMP推流实战：从原理到118克盒子部署

RK3528+1GB内存如何变身直播节点？硬编解码与六协议实战复盘

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？