“谁考了第k名”——这道题在各大OJ里的出镜率实在太高。我第一次在机房翻学生提交记录时发现一个特别有意思的现象题目名越直白越容易被轻视结果一排红色的错误里最常见的不是不会排序而是把“第1名”当成数组里的第1个元素来输出。为了把话说明白我按当前信息学入门题最常见的题目设定来讲先输入一个整数n接下来n行每行是一个学生的学号字符串和成绩整数最后输入一个整数k要求输出排名第k的那个学生的学号与成绩。这篇文章会把读题、选型、写码、自查的完整链路拆开讲适合刚学排序的新手也适合带竞赛选手入门的教练。这道题看起来简单但它在不同教材里会变着花样出现一会儿叫“成绩排序”一会儿叫“谁考了第k名”一会儿要求只排前几名。不管名字怎么变核心就两条第一学生信息是一个整体学号和成绩必须绑在一起移动第二所谓第k名是“排名意义上的位置”不是输入顺序里的位置。把这两条刻在脑子里这道题就已经拿下一半。1. 先啃透题意“第k名”的三层隐藏信息很多学生拿到这题就直接写sort写完才发现输出对不上。原因很简单题面没读透。这里说的“读题”不是逐字看输入输出格式而是把题面里藏着的数据组织方式、边界条件、同分规则都揪出来。1.1 名次对应的是排序后的位置不是输入顺序第k名听起来像是一个“选项”实际上它是一个“位置”。你要做的不是在第k个输入的人里找答案而是把所有学生按成绩从高到低排列再去取排在第k个的那个学生。这和“按输入顺序输出第k个人”完全是两码事区分不清楚的话样例都过不了。我见过不少初学者把k当成输入的序号直接stu[k]输出这就是典型的“题目没读懂”。排序的意义在于它把每个学生原本在输入序列中的位置转换为排名序列中的一个新位置。这是整道题成立的根基。1.2 第一名对应数组下标0一半的错误都出在这里如果说读题是第一关那下标差一就是第二关。数组下标从0开始当k等于1时你要输出的是排序后数组中下标为0的那个学生也就是stu[0]k等于5时对应stu[4]。公式就一个stu[k-1]。我给几个具体例子目标排名k正确下标错误写法第一名10stu[1]第三名32stu[3]最后一名nn-1stu[n]这个错误低级却高频因为题目描述里用的是“第几名”而代码里用的是“第几个元素”。人脑用自然语言思考计算机用下标寻址两者中间的转换就是差一错误的重灾区。以后做排名相关题目第一反应永远应该是排名转下标要减1。1.3 同分规则题目没写时你至少要有个默认策略“成绩相同怎么办”这个问题十个题目有八个不会明说。但实际排序时你的sort一定会遇到两个成绩相等的元素它总得决定谁先谁后。不同题目的潜台词通常有几种默认按输入顺序、要求按学号升序、要求并列名次但输出顺序任意。以“谁考了第k名”这道题最常见的设定来说同分时往往没有额外要求或者要求学号小的在前。我个人的默认策略是主关键字成绩降序辅关键字学号升序。这样一来成绩相同也有唯一确定的前后关系输出结果稳定、可复现不会因为编译器版本或sort内部实现变化而出现悬而未决的答案。提示做题前先想清楚同分规则不是过度设计。它会让你的比较器有确定的语义也让你在OJ反馈Wrong Answer时少一个可怀疑的方向。2. 排序选型为什么我建议先稳住sort而不是手写花活排序算法学了冒泡、选择、插入、快排、归并之后很多学生反而不知道怎么选了是不是该自己实现一个快速排序来证明实力我的建议很直接竞赛和日常开发优先用语言自带的排序接口手写排序用来理解原理不用于交题。2.1 复杂度对比O(n log n)到底比O(n²)快多少以n10万为例std::sort的比较次数大约是n乘log2(n)也就是100000乘17约170万次比较。而冒泡排序在最坏情况下需要约n²/2次比较也就是50亿次。这两者的差距不是“快一点”和“慢一点”的区别是“毫秒级”和“几分钟都跑不完”的区别。如果n再往上走比如到100万sort大约需要2000万次比较依然在可接受范围内冒泡则需要5000亿次彻底不可行。所以复杂度分析的意义在于让你一眼判断一个问题用什么算法能过什么算法必然超时。数据规模手写冒泡最坏sort / 归并类n1000约50万次比较约1万次比较n100000约50亿次比较约170万次比较n1000000约5000亿次比较约2000万次比较这不是说冒泡没有存在价值而是说它在小样本和特定场景下更直观。但到了“谁考了第k名”这种规模不确定的题直接用封装好的高效排序是更稳的选择。2.2 自定义比较器的核心认知返回true就是“a要排在b前面”C里用sort自定义排序很多人绕不过去的是比较器怎么写。只要记住一句话cmp(a, b)返回true表示a应该排在b前面返回false表示a不应该排在b前面。有了这个认知锚点写起来就不容易反。比如要实现“成绩高的在前”就是a.score b.score的时候返回true因为分数高的确实应该排在分数低的前面。要实现“成绩相同的学号小的在前”就再嵌套一层判断成绩相等时如果a.id b.id返回true。bool cmp(const Student a, const Student b) { if (a.score ! b.score) { return a.score b.score; } return a.id b.id; }这段代码里主要判断是成绩降序次要判断是学号升序。整个比较器的逻辑是确定的任何两个学生都能分出先后不会出现互相矛盾的情况。2.3 严格弱序看似枯燥却是比较器的隐藏红线std::sort要求比较器满足“严格弱序”性质。这个概念听起来很学术但它对应的问题非常实际如果cmp(a, b)返回true同时cmp(b, a)也返回true排序结果就是未定义的程序可能崩溃可能乱序也可能出现难以复现的怪问题。拿成绩排序举例如果只写return a.score ! b.score当两人分数相等时这个表达式返回falsea和b谁在前交给算法内部决定这没问题。怕的是你写出return a.score b.score这种带等号的比较它会让相等的元素互相认为对方应该排在自己前面破坏了严格弱序。所以比较器里相等情况的返回值一定要统一为false不要用或。这个细节不注意到小数据可能没事数据一多、递归一深问题就浮出来了。3. 让学号和成绩“焊”在一起三种数据组织方式的对决题目真正考察的第二个重点是如何让一个学生的所有属性在排序过程中保持绑定关系。这里有三条路对应三种常见写法踩坑程度完全不同。3.1 两个独立数组排序一时爽回溯两行泪最朴素的想法是开两个数组一个存学号一个存成绩然后用某种方式记录排序后的对应关系。int score[N]; string id[N];然后呢你交换score的时候必须同步交换id。一旦忘记所有学生的学号和成绩就全面错位。这种“双数组同步维护”的错误我在竞赛环境里见过无数次而且错得很隐蔽成绩整体还是降序看起来排对了但输出的学号全是乱的因为你交换成绩时没带上学号。有人会想那我交换成绩时记住学号下标不就行了可以但你要额外维护一个下标数组也就是pos每次交换都同步交换三个数组。代码复杂度和心智负担立刻上去了对初学者来说完全不值得。3.2 结构体方案一个人物模型一套信息正确姿势是把学号和成绩打包成一个结构体struct Student { string id; int score; };这样排序时交换的是一个完整的Student对象学号和成绩永远一起移动。代码可读性也高stu[i].score一眼就知道是第i个学生的成绩而不是“成绩数组的第i个元素”。结构体的意义不只是代码美观它让你把“学生”当成一个整体来思考。以后题目里加字段比如姓名、班级、性别你只需要在结构体里加成员排序和输出的逻辑骨架不变。这就是为什么我说结构体排序不只是这道题的解法它是后续几乎所有“记录处理”类题目的地基。3.3 pair和元组简洁背后的默认排序规则C里的pair和Python里的元组提供了另一种打包思路。它们的好处是省去结构体定义坏处是默认排序规则不一定符合你的需求。std::pair排序时先比第一个元素再比第二个元素而且默认都是升序。想按成绩降序要么把成绩取负存成pairint, string要么写自定义比较器。Python元组的sorted默认规则同理通常会用keylambda x: -x[1]来反转。用pair本身没错但你要时刻记得它的默认规则。很多时候学生写sort(a, a n)发现顺序反了就是因为只存了学号和成绩的pair却忘了pair是先按学号排的。结构体方案虽然多写几行但是每个条件都看得清清楚楚翻车概率小得多。4. 数据规模与效率sort是不是永远够用入门题的数据范围一般不会太变态但既然是聊效率就得把“够用”的边界说清楚。免得你哪天碰上一道卡常的题还在那儿硬跑sort。4.1 从log n出发估算一道题能接受多大n判断排序能不能过先看两个数数据规模n以及一场考试/一次提交的时间限制通常是1秒到2秒。sort的时间复杂度是O(n log n)这里的log底数是2n等于10万时log n大约是1710万乘17约170万n等于100万时是2000万n等于1000万时大约是2.3亿。2.3亿次比较在1秒多钟内不是一定跑不完但加上内存分配、用户输入、比较器调用开销就很吃紧了。到了这个规模就要考虑空间和常数的优化。所以在入门阶段你可以记住一个粗略结论n在10万以内sort闭眼用n到了100万还能用但要留意实现细节n到了1000万优先想别的办法。4.2 nth_element与部分排序不想全排时的一招题目只问第k名并不需要完整排名。C里有个函数叫std::nth_element它做的事情是经过重排后第k个位置上的元素就是整个序列中第k小的元素但它不保证前后有序。nth_element(stu.begin(), stu.begin() k - 1, stu.end(), cmp);这样调完之后stu[k-1]就是答案复杂度期望是O(n)。在n很大、且只输出一个答案的场景下它比全排序更快。不过我不建议初学者在“谁考了第k名”里用它原因有两点。第一nth_element不保证排序结果稳定部分OJ会拿完整的成绩单样例来验证你只拿到第k个是对的但其他位置对不对无法预知第二你迟早会遇到“先求第k名再输出前k名”的变体题那时候nth_element就不好用了。先把sort用熟练再了解nth_element顺序不要反。4.3 稳定性的现实意义默认排序和stable_sort的差异std::sort不保证稳定意思是两个成绩相同的元素排序前后相对顺序可能变化。std::stable_sort则能保证相等元素保持原来的相对位置。Python里的list.sort()和sorted()默认就是稳定的这一点和C默认不同很多人会踩跨语言的坑。需要稳定排序的典型场景就是题目隐含“同分按输入顺序输出”。如果你用Csort直接排同分元素之间的顺序不受你控制改用stable_sort或者更通用一点在结构体里加一个order字段同分时按order升序这样不管用什么排序函数结果都可控。struct Student { string id; int score; int order; // 输入时的顺序 }; bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.order b.order; }这个技巧看着简单却是处理“名次并列”“指定顺序”类题目的通用解。它比stable_sort更可控因为你是显式地告诉排序算法“同分时谁先谁后”而不是依赖排序函数的内部保证。5. C与Python的完整实现从输入到输出一次跑通下面给出两份可以直接提交的代码。我按“学号为字符串、成绩为整数”的常见设定来写注释里会说明怎么改成浮点成绩。5.1 C方案结构体 sort 自定义比较器#include bits/stdc.h using namespace std; struct Student { string id; int score; }; bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n; vectorStudent stu(n); for (int i 0; i n; i) { cin stu[i].id stu[i].score; } cin k; sort(stu.begin(), stu.end(), cmp); cout stu[k - 1].id stu[k - 1].score \n; return 0; }这里的三个动作非常清晰读入所有学生到vector调用sort排序输出stu[k-1]。唯一需要你注意的就是cmp函数里返回值的语义成绩不同时分数高的排前面成绩相同时学号小的排前面。如果题目说成绩相同不要求顺序你可以把第二个条件删掉但那样输出在极端情况下可能与出题人的数据不一致所以我一般保留学号升序。5.2 Python方案sorted(keylambda ...) 的简洁与隐患import sys def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) students [] idx 1 for _ in range(n): sid data[idx] score int(data[idx 1]) idx 2 students.append((sid, score)) k int(data[idx]) students.sort(keylambda x: (-x[1], x[0])) ans students[k - 1] print(ans[0], ans[1]) if __name__ __main__: main()Python用sort(key...)排序key函数返回一个元组第一项是负分第二项是学号。这样元组排序时会先按-score升序相当于按score降序分一样时再按学号升序。这个技巧写起来非常简洁但要注意负号不要漏漏了就变成升序了。如果你不喜欢负数技巧也可以不写key改用cmp_to_key自定义比较器但代码更长可读性反而下降。我个人更推荐key函数方案它是Python社区的主流写法。5.3 输入输出细节cin关同步、sys.stdin.read一次性读取C里如果只用cin读数据记得加这两行ios::sync_with_stdio(false); cin.tie(nullptr);原因很简单默认情况下cin和scanf要保持同步导致每次读入都很慢。关了同步之后cin会快很多配合cout的\n而不是endl能省下大量时间。endl会额外刷新输出缓冲区竞赛里没这个必要。Python输入方面如果数据量不大input()逐行读也没问题但如果n到了10万以上更稳的做法是用sys.stdin.read()一次性把全部数据读进来再切分也就是我上面代码里的写法。它比逐行input()快一个量级而且也不用担心末尾换行符带来的解析问题。读完整个文件再统一处理代码逻辑反而更集中。6. 提交即错五个常见坑的复盘与修复最后这部分我按自己在OJ和比赛里看到的高频错误一条条复盘。每一条都对应一个具体的代码习惯改起来很快但不知道的话能卡你很久。6.1 下标差一k1时输出 stu[1] 还是 stu[0]这个问题在第一部分已经提过但它实在太高频了必须在复盘里单列一次。输入k1正确的输出是排序后第一个元素也就是下标0。一个有效的自查办法是用k1和kn两个边界各测一遍。如果你使用stu[k]k1时会输出第二名kn时直接越界。运行后者如果报Segmentation fault或IndexError基本就是下标公式错。把它改成stu[k-1]两个边界就都对了。6.2 把末尾的k读成了第n1条学生记录题目输入顺序是n、n行学生、k。有些人在读学生信息时循环就写成for (int i 0; i n; i)结果把k也当成一个学生读进去了后面的cin k读到的是空或者下一组数据输出自然乱套。正确的循环一定是for (int i 0; i n; i)读完之后再单独读k。Python里使用sys.stdin.read()解析时则要格外小心索引位置学生循环用掉2*n个元素后接下来的那一个才是k。为了方便定位可以像我的示例代码那样用idx变量显式追踪当前位置读一个往前走一步。6.3 成绩是浮点数时的精度与格式化输出有些版本的成绩是整数有些是浮点数。如果是后者注意两点。第一存储用double不要用floatfloat只有约6到7位有效十进制精度成绩里有小数位时可能出错。第二输出格式务必和题目要求一致比如“保留两位小数”那么C里要用fixed setprecision(2)或者printf(%.2f, ...)Python里用f{score:.2f}。这里有一个隐藏坑printf(%.2f)依赖当前舍入模式一般是四舍五入如果OJ数据里卡一个特殊小数比如0.005这类边界精度不同语言和编译器的处理可能不同。稳妥做法是看完题目是否明确给定样例格式如果没给就按原始值原样输出别自己加格式化。6.4 sort不稳定引发的“同分顺序问题”成绩相同的时候sort不保证维持输入顺序stable_sort才保证。如果你发现某次提交AC换一个编译器版本提交却WA或者本地跑结果和OJ结果不一致那多半就是同分顺序问题。解法我已经提过给结构体加order字段同分按order升序。这个字段是“输入序号”从0或1开始都行只要保证同分时和输入顺序一致。代码只多两行但从此排序结果完全可控不再依赖算法内部实现。6.5 多组测试数据和空行的处理部分题目会写成“输入包含多组测试数据每组第一行是n文件以EOF结束”而不是只测一组。这时C的标准写法是int n; while (cin n) { vectorStudent stu(n); for (int i 0; i n; i) { cin stu[i].id stu[i].score; } int k; cin k; sort(stu.begin(), stu.end(), cmp); cout stu[k - 1].id stu[k - 1].score \n; }这里的while (cin n)会在读不到数据时自动退出不用手动处理空行。Python用sys.stdin.read()解析时空行会被split()自动忽略所以也不用做特殊处理。只要你按“读取位置游标”的方式移动多组数据无非就是多循环几次。最后说点带实际比赛体会的结构体排序看起来是入门题但很多人在校赛、CSP、蓝桥杯的入门题上翻车恰恰就是翻在排名和下标的关系上。我自己的习惯是动手前先在草稿纸上写出“输入格式——排序字段——输出字段”三行字再考虑要不要加结构体、比较器怎么写。这套笨办法帮我省了无数次返工。如果你想把这道题再往前推一步可以试试把输出从“第k名”改成“完整成绩单分数相同的并列名次”。也就是1、2、2、4这样的名次序列你会发现需要维护的变量一下子变多了你也会更清楚现在练好的结构体排序到底在给什么打地基。