1. 从“复试筛选”这个标题说起它到底在考什么第一次看到“XDOJ 170-复试筛选”这个标题很多人会以为这是一道关于考研复试流程的模拟题或者是一个筛选简历的算法题。实际上在编程练习平台的语境下这类题目通常属于模拟类或排序筛选类问题。它的核心不是考你懂不懂复试政策而是考你如何用代码实现一套多条件排序与筛选逻辑。我当年第一次做这道题的时候也被“复试”两个字带偏了以为要处理什么复杂的文本匹配。后来把题目读完才发现它本质上是一个结构化数据的多关键字排序问题。题目通常会给你一组考生数据每条数据包含准考证号、姓名、初试成绩、复试成绩等信息然后要求你按照一定的规则筛选出进入下一轮的人选并按照指定顺序输出。这类题在编程练习中非常经典因为它同时考察了几个核心能力数据结构的选型、排序规则的实现、边界条件的处理。而且“复试筛选”这个场景天然带有现实意义——它模拟的就是真实招生工作中按比例划定名额、按成绩排名录取的流程。所以它不只是一道算法题更是一个用代码解决实际筛选问题的微型项目。这篇文章我会从题目理解、数据结构设计、排序逻辑拆解、边界情况处理、代码实现与优化、常见踩坑点这几个维度把这道题彻底讲透。无论你是刚接触编程练习的新手还是想复习排序与筛选套路的老手都能从中拿到可以直接复用的思路和代码模板。提示不同平台上的题目描述可能有细微差异本文以“多条件排序筛选”这一通用模型为主线展开具体输入输出格式请以你实际看到的题目为准。2. 题目背后的数据模型先想清楚要处理什么2.1 输入数据的典型结构这类题目一般会先给一个整数 N表示考生人数。接下来 N 行每行包含若干字段。常见的字段组合有以下几种字段名类型说明准考证号字符串或整数唯一标识通常用于最终输出姓名字符串可能包含在输出中也可能只是干扰项初试成绩整数第一轮成绩复试成绩整数第二轮成绩总成绩整数或浮点数可能是初试复试也可能是加权计算有些题目会直接给出总成绩有些则要求你自己计算。如果是加权计算常见的权重比如初试占 70%、复试占 30%或者各占 50%。这时候就需要注意整数除法与浮点数精度的问题。我个人的习惯是先把所有可能用到的字段都读进来存到一个结构体或类里。即使某些字段暂时用不到后面万一需要排序或输出也不用回头改读取逻辑。2.2 筛选规则的本质“筛选”这个词听起来很业务化但在代码层面它通常就是按某个阈值或排名比例截断。常见的筛选规则有两类按比例筛选比如计划录取 M 人按 1:1.2 或 1:1.5 的比例确定进入复试的人数。如果 M10比例 1:1.5那么进入复试的人数就是 15 人。按分数线筛选比如总分不低于 X 分且单科不低于 Y 分。这种规则通常用于初试筛选复试筛选更常见的是按比例。如果是按比例筛选就涉及到一个向上取整还是向下取整的问题。比如 10 × 1.2 12没问题但 11 × 1.2 13.2是取 13 还是 14不同题目的规定可能不同有的要求“至少”那就向上取整有的要求“不超过”那就向下取整。这个细节必须看清楚否则会错在边界上。2.3 排序规则的优先级筛选之前通常要先排序。排序规则往往是多关键字的比如先按总成绩从高到低总成绩相同按初试成绩从高到低初试成绩也相同按准考证号从小到大。这种多关键字排序是这道题的核心考点之一。很多编程语言都提供了自定义比较函数的能力但不同语言的写法差异很大。比如 C 语言的qsort需要写一个返回 int 的比较函数C 的sort可以传 lambdaPython 的sorted可以用key参数配合元组Java 则需要实现Comparator接口。我见过不少人在这一步翻车不是因为逻辑想错了而是因为比较函数的返回值写反了或者没有处理好相等的情况导致排序结果不稳定。下面我会专门用一节来讲比较函数的写法。3. 排序比较函数多关键字排序的三种实现套路3.1 为什么比较函数容易写错先看一个典型的错误写法。假设要求按总成绩降序、初试成绩降序、准考证号升序排列。有人可能会写成这样int cmp(const void *a, const void *b) { Student *s1 (Student *)a; Student *s2 (Student *)b; if (s1-total ! s2-total) return s1-total - s2-total; // 错误降序应该反过来 if (s1-initial ! s2-initial) return s1-initial - s2-initial; return s1-id - s2-id; }这段代码的问题在于s1-total - s2-total返回正数时表示 s1 排在 s2 后面也就是升序。但题目要求降序所以应该写成s2-total - s1-total。这种“符号写反”的错误非常隐蔽因为排序结果看起来“差不多”只是顺序反了如果不仔细核对样例输出很容易漏掉。3.2 套路一逐级比较显式返回最稳妥的写法是逐级比较每一级都明确写出返回条件int cmp(const void *a, const void *b) { Student *s1 (Student *)a; Student *s2 (Student *)b; if (s1-total ! s2-total) return s2-total - s1-total; // 总成绩降序 if (s1-initial ! s2-initial) return s2-initial - s1-initial; // 初试降序 return s1-id - s2-id; // 准考证号升序 }这种写法的好处是逻辑清晰每一级的排序方向一目了然。缺点是代码略长但胜在不容易出错。我在实际做题时除非字段特别多否则都会用这种写法。3.3 套路二用元组或复合键简化在 Python 中可以利用元组的比较特性把多关键字排序写成一行students.sort(keylambda s: (-s.total, -s.initial, s.id))这里的-s.total表示降序s.id表示升序。Python 的元组比较是从左到右逐项比较正好对应多关键字排序的优先级。这种写法非常简洁但要注意取负号只适用于数值类型如果字段是字符串就不能直接取负需要用reverse参数或者自定义包装类。C 也可以用tie或者make_tuple来简化sort(students.begin(), students.end(), [](const Student a, const Student b) { return tie(b.total, b.initial, a.id) tie(a.total, a.initial, b.id); });这里用tie把多个字段绑成一个元组然后利用元组的字典序比较。注意降序字段要放在前面并交换 a、b 的位置升序字段放在后面保持原序。这种写法很优雅但可读性稍差适合对 C 比较熟悉的同学。3.4 套路三自定义结构体运算符在 C 中还可以直接重载结构体的运算符struct Student { int id, initial, total; bool operator(const Student other) const { if (total ! other.total) return total other.total; if (initial ! other.initial) return initial other.initial; return id other.id; } };这样在调用sort时就不需要传比较函数了直接sort(students.begin(), students.end())即可。这种写法适合需要多次排序同一结构的场景把排序规则内聚到结构体内部调用方更省心。注意无论用哪种套路都要确保比较函数满足严格弱序。简单说就是不能出现a b和b a同时为真的情况也不能出现a a为真的情况。逐级比较的写法天然满足这个条件但如果你用了复杂的表达式就要多留个心眼。4. 筛选环节的边界处理比例、并列与截断4.1 按比例计算名额时的取整问题假设题目说“按 1:1.2 的比例确定进入复试名单”计划录取 M 人。那么进入复试的人数应该是ceil(M * 1.2)还是floor(M * 1.2)这个必须看题目原文。如果题目说“不少于”那就是向上取整如果说“不超过”那就是向下取整。在 C/C 中整数除法默认是向下取整所以计算M * 12 / 10得到的是 floor 的结果。如果需要 ceil可以写成(M * 12 9) / 10。这个技巧很常用但要注意整数溢出如果 M 很大M * 12 可能超出 int 范围这时候要用 long long。Python 中可以用math.ceil(M * 1.2)但要注意浮点数精度问题。比如0.1 0.2 ! 0.3这种经典问题在比例计算中也可能出现。更稳妥的做法是用整数运算(M * 12 9) // 10。4.2 并列名次怎么处理这是筛选类题目最容易出坑的地方。假设计划录取 10 人按 1:1.2 比例进入复试 12 人。但第 12 名和第 13 名总成绩相同那第 13 名要不要进不同题目的规定不同严格按名额只取前 12 人即使第 13 名同分也不进。并列全进只要和第 12 名同分就一起进实际人数可能超过 12。并列看下一关键字如果总成绩相同就比较初试成绩初试也相同再比较准考证号直到分出先后。我遇到过的大多数题目采用的是第三种也就是通过多关键字排序保证没有并列。因为准考证号通常是唯一的所以最后一级比较总能分出胜负。这样一来就不存在“同分要不要进”的问题了直接取前 K 人即可。但如果题目明确说“总成绩相同则并列”那就需要特殊处理。这时候通常要求输出所有并列的考生实际人数可能超过计划名额。处理方法是先排序然后从第 K 个人开始往后检查是否和第 K 个人同分如果是就一起加入名单。4.3 输出格式的坑筛选完之后输出格式也有讲究。常见的要求有按排名顺序输出每行一个考生的信息。只输出准考证号或者输出完整信息。如果人数不足输出实际人数。行末不能有多余空格。这些细节看似琐碎但在在线评测系统中格式错误和答案错误是分开判定的。我见过不少人算法完全正确但因为多输出了一个空格或者少输出了一个换行导致反复提交不通过。建议在本地测试时用diff命令对比自己的输出和样例输出确保完全一致。5. 完整代码实现从读取到输出的全流程5.1 C 版本结构体 sort 筛选下面是一个完整的 C 实现框架假设题目要求按总成绩降序、初试降序、准考证号升序排序然后取前 K 人输出。#include iostream #include vector #include algorithm #include cmath using namespace std; struct Student { int id; int initial; int retest; int total; }; int main() { int n; cin n; vectorStudent students(n); for (int i 0; i n; i) { cin students[i].id students[i].initial students[i].retest; students[i].total students[i].initial students[i].retest; } sort(students.begin(), students.end(), [](const Student a, const Student b) { if (a.total ! b.total) return a.total b.total; if (a.initial ! b.initial) return a.initial b.initial; return a.id b.id; }); int m; cin m; // 计划录取人数 int k (m * 12 9) / 10; // 按1:1.2向上取整 if (k n) k n; cout k endl; for (int i 0; i k; i) { cout students[i].id students[i].total endl; } return 0; }这段代码的核心逻辑很清晰读入、计算总分、排序、计算名额、输出。但有几个细节值得展开说。第一total字段是在读入时计算的而不是在比较函数里现算。这样做的好处是比较函数更轻量排序更快。如果数据量很大比如 N 达到 10 万在比较函数里重复计算总分会导致性能下降。第二名额计算用了(m * 12 9) / 10这是向上取整的整数写法。如果 m 很大m * 12 可能溢出 int所以更稳妥的做法是把 m 声明为long long或者用(m * 6 4) / 5这种更小的乘数。第三输出时先输出实际人数 k再输出每个人的信息。有些题目不要求输出人数直接输出名单即可这个要根据题目要求调整。5.2 Python 版本简洁但要注意性能Python 的写法会更简洁n int(input()) students [] for _ in range(n): parts input().split() sid int(parts[0]) initial int(parts[1]) retest int(parts[2]) students.append((sid, initial, retest, initial retest)) students.sort(keylambda s: (-s[3], -s[1], s[0])) m int(input()) k (m * 12 9) // 10 k min(k, n) print(k) for i in range(k): print(students[i][0], students[i][3])Python 的元组排序非常方便但要注意当数据量很大时Python 的排序速度可能成为瓶颈。如果 N 达到 10 万以上建议用sys.stdin.read().split()一次性读入所有数据避免逐行input()的开销。另外lambda中的负号取反只适用于数值如果字段是字符串需要用functools.cmp_to_key自定义比较函数。5.3 处理并列的扩展写法如果题目要求并列全进可以在排序后这样处理int k (m * 12 9) / 10; if (k n) k n; // 检查第k名之后是否有同分 while (k n students[k].total students[k-1].total) { k; }这段代码的逻辑是先按名额算出 k然后从第 k 个位置开始往后看只要总成绩和前面一个人相同就继续扩大名单。注意这里比较的是students[k].total和students[k-1].total因为数组是从 0 开始索引的第 k 个人实际上是第 k1 名。这种写法假设排序已经保证了同分的人排在一起。由于我们用了多关键字排序同分的人会按照后续关键字排列所以这个假设是成立的。6. 我踩过的坑与排查思路6.1 排序结果“看起来对”但就是不过这是最让人头疼的情况。样例输入输出完全一致但提交就是 Wrong Answer。我遇到过的原因有几种原因一比较函数没有处理完全相等的情况。比如只比较了总成绩和初试成绩没有比较准考证号。当两个考生所有成绩都相同时比较函数返回 0排序算法可能认为它们相等但题目要求按准考证号升序。这种情况下样例可能恰好没有完全相同的考生所以本地测试通过但评测数据里有就挂了。排查方法构造一组所有字段都相同的测试数据看看输出顺序是否符合预期。如果不符合说明比较函数缺少最后一级。原因二整数溢出。比如总成绩是初试 复试两个都是 int 范围内的数但相加后可能溢出。如果题目数据范围很大要用 long long。排查方法把 int 改成 long long重新提交。如果过了就是溢出问题。原因三输出格式的细微差异。比如行末多了空格或者最后一行没有换行。有些评测系统对格式非常敏感。排查方法用cat -A查看自己的输出和样例输出的不可见字符确保完全一致。6.2 比例计算取整方向搞反这个坑我踩过不止一次。题目说“按 1:1.2 的比例确定复试名单”我下意识用了向下取整结果实际名额比预期少了一个。后来仔细读题发现题目说的是“不少于计划录取人数的 1.2 倍”那就应该向上取整。经验看到比例先找关键词。“不少于”“至少”对应向上取整“不超过”“最多”对应向下取整。如果题目没有明确说就看样例用样例数据算一下看看哪种取整方式能得到样例输出。6.3 数据量大的时候超时如果 N 达到 10 万甚至 100 万O(N log N) 的排序本身没问题但输入输出可能成为瓶颈。C 中可以用scanf/printf代替cin/cout或者加上ios::sync_with_stdio(false)来加速。Python 中可以用sys.stdin.read()一次性读入。另外如果比较函数里做了复杂计算比如每次都比较字符串也会拖慢排序。尽量把能预先计算的字段算好存起来比较函数只做简单的数值比较。6.4 准考证号是字符串时的排序问题有些题目的准考证号是字符串比如 “2024001”。如果按字符串排序会出现 “20240010” 排在 “2024002” 前面的情况因为字符串比较是逐字符的。如果题目要求按数值排序就需要先把字符串转成整数或者用补零的方式保证长度一致。经验看到准考证号先确认它是作为字符串还是数值处理。如果题目说“按准考证号从小到大”通常指的是数值顺序除非准考证号包含字母。7. 从这道题能学到什么可迁移的解题套路7.1 多关键字排序的通用模板这道题的核心是多关键字排序这个套路可以迁移到很多场景学生成绩排名按总分、单科、学号排序。员工绩效排序按绩效、工龄、工号排序。商品列表排序按销量、价格、上架时间排序。通用模板就是逐级比较先比优先级高的字段相等再比下一级直到分出胜负或所有字段都比完。在 C 中用 lambda 或比较函数在 Python 中用元组或cmp_to_key在 Java 中用Comparator。7.2 筛选类问题的通用思路筛选类问题的通用思路是先排序再按规则截断。排序保证了“优者在前”截断实现了“取前 K 个”。如果涉及并列就在截断后做一次扩展检查。这个思路可以迁移到排行榜取前 N 名。奖学金评定按比例划定名额。面试筛选按分数线和比例确定人选。7.3 边界条件的检查清单每次做完这类题我都会用以下清单检查一遍检查项说明比较函数是否覆盖所有字段确保没有遗漏最后一级比较取整方向是否正确向上还是向下看题目关键词名额是否超过总人数取 min(k, n)并列是否处理看题目是否要求并列全进输出格式是否一致空格、换行、行末字符数据范围是否溢出int 够不够要不要 long long输入输出是否够快大数据量时用快速 IO这份清单看起来简单但每次做题前过一遍能避免 80% 的低级错误。7.4 从“做题”到“做项目”的思维转变最后说一点个人体会。这道题虽然是一道编程练习题但它模拟的是一个真实的筛选流程。如果你把它当成一个微型项目来做就会自然而然地考虑更多问题数据怎么存、规则怎么抽象、边界怎么处理、输出怎么格式化。这些思考方式和做真实项目是一样的。我在实际工作中遇到过类似的筛选需求比如从一批候选人中按多维度评分选出进入下一轮的人。当时我就是套用了这道题的思路先定义数据结构再实现多关键字排序最后按名额截断并处理并列。代码写出来不到 100 行但逻辑非常清晰后续维护也很方便。所以别小看这道“复试筛选”题。它考的不只是排序而是用代码实现一套完整筛选逻辑的能力。把这个能力练熟了遇到类似的业务需求你就能快速拿出可靠的方案。