企业官网建设流程全解析

“谁考了第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]。

我给几个具体例子：

这个错误低级却高频，因为题目描述里用的是“第几名”，而代码里用的是“第几个元素”。人脑用自然语言思考，计算机用下标寻址，两者中间的转换就是差一错误的重灾区。以后做排名相关题目，第一反应永远应该是：排名转下标要减1。

1.3 同分规则：题目没写时你至少要有个默认策略

“成绩相同怎么办？”这个问题，十个题目有八个不会明说。但实际排序时，你的sort一定会遇到两个成绩相等的元素，它总得决定谁先谁后。

不同题目的潜台词通常有几种：默认按输入顺序、要求按学号升序、要求并列名次但输出顺序任意。以“谁考了第k名”这道题最常见的设定来说，同分时往往没有额外要求，或者要求学号小的在前。我个人的默认策略是：主关键字成绩降序，辅关键字学号升序。这样一来，成绩相同也有唯一确定的前后关系，输出结果稳定、可复现，不会因为编译器版本或sort内部实现变化而出现悬而未决的答案。

提示：做题前先想清楚同分规则，不是过度设计。它会让你的比较器有确定的语义，也让你在OJ反馈Wrong Answer时，少一个可怀疑的方向。

2. 排序选型：为什么我建议先稳住sort，而不是手写花活

排序算法学了冒泡、选择、插入、快排、归并之后，很多学生反而不知道怎么选了：是不是该自己实现一个快速排序来证明实力？我的建议很直接：竞赛和日常开发，优先用语言自带的排序接口；手写排序用来理解原理，不用于交题。

2.1 复杂度对比：O(n log n)到底比O(n²)快多少

以n=10万为例，std::sort的比较次数大约是n乘log2(n)，也就是100000乘17，约170万次比较。而冒泡排序在最坏情况下需要约n²/2次比较，也就是50亿次。这两者的差距，不是“快一点”和“慢一点”的区别，是“毫秒级”和“几分钟都跑不完”的区别。

如果n再往上走，比如到100万，sort大约需要2000万次比较，依然在可接受范围内；冒泡则需要5000亿次，彻底不可行。所以复杂度分析的意义在于，让你一眼判断一个问题用什么算法能过，什么算法必然超时。

这不是说冒泡没有存在价值，而是说它在小样本和特定场景下更直观。但到了“谁考了第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，当两人分数相等时，这个表达式返回false，a和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排序时，先比第一个元素，再比第二个元素，而且默认都是升序。想按成绩降序，要么把成绩取负存成pair<int, string>，要么写自定义比较器。Python元组的sorted默认规则同理，通常会用key=lambda 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底数是2，n等于10万时log n大约是17，10万乘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++默认不同，很多人会踩跨语言的坑。

需要稳定排序的典型场景，就是题目隐含“同分按输入顺序输出”。如果你用C++sort直接排，同分元素之间的顺序不受你控制；改用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; vector<Student> 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(key=lambda ...) 的简洁与隐患

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(key=lambda 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 下标差一：k=1时输出 stu[1] 还是 stu[0]

这个问题在第一部分已经提过，但它实在太高频了，必须在复盘里单列一次。输入k=1，正确的输出是排序后第一个元素，也就是下标0。

一个有效的自查办法是：用k=1和k=n两个边界各测一遍。如果你使用stu[k]，k=1时会输出第二名，k=n时直接越界。运行后者如果报Segmentation fault或IndexError，基本就是下标公式错。把它改成stu[k-1]，两个边界就都对了。

6.2 把末尾的k读成了第n+1条学生记录

题目输入顺序是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，不要用float，float只有约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) { vector<Student> 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这样的名次序列，你会发现需要维护的变量一下子变多了，你也会更清楚现在练好的结构体排序，到底在给什么打地基。