1. 从一道题看复试筛选的底层逻辑
第一次看到“XDOJ 170-复试筛选”这个标题，很多人会以为它只是一道普通的排序题。但真正做过这道题、并且带过几届考研学生之后，我发现它其实是一道披着排序外衣的多条件筛选与稳定排序综合题。它模拟的是研究生复试阶段最核心的一个环节：在初试成绩公布之后，如何从一批达到基本分数线的考生中，按照既定规则筛选出进入复试的名单。
这道题的核心关键词是“复试筛选”，它要解决的问题非常明确：给定若干考生的初试总分、单科成绩和报考方向，按照学校公布的复试规则，判断哪些人能够进入复试，并按照规则输出名单。听起来简单，但里面藏着几个容易翻车的点：单科线是否必须全部过线、总分相同的时候怎么排、不同方向是否分开排名、以及“筛选”这个词到底意味着只输出合格的人还是输出所有人的状态。
适合谁来参考这篇内容？如果你是正在准备计算机相关专业复试的考生，这道题能帮你理解复试筛选的规则设计；如果你是带学生的老师或者助教，这道题可以作为讲解排序与多条件判断的经典案例；如果你只是单纯在刷算法题，这道题能让你把结构体排序、多关键字比较、边界条件处理这几个基本功练扎实。我见过太多人在这道题上栽跟头，不是不会排序，而是没把规则吃透。
提示：这道题在不同版本的题库中可能有细微的输入输出差异，但核心逻辑是一致的。下面我以最常见的版本为例展开，如果你遇到的版本有出入，重点看规则解析部分，那才是通用的。
2. 题目规则拆解与常见理解偏差
2.1 复试筛选的规则到底在说什么
先把这道题的规则用大白话翻译一遍。通常题目会给出几个关键参数：国家线总分、单科线、以及每个考生的各科成绩。一个考生要进入复试，必须同时满足两个条件：总分不低于国家线，并且每一门单科成绩都不低于对应的单科线。这两个条件是“与”的关系，缺一不可。
我见过很多人的第一反应是“总分够了就行”，或者“单科差一点但总分高可以弥补”。这两种理解都是错的。复试筛选的第一道门槛就是硬性条件，没有任何通融余地。这就像你去坐飞机，机票买好了、行李也托运了，但安检没过就是上不了飞机，总分再高也没用。
题目还会要求输出进入复试的名单，并且按照一定的规则排序。常见的排序规则是：先按总分从高到低排，总分相同的按某一门单科成绩从高到低排，如果还相同则按另一门单科成绩排，最后如果所有成绩都相同，可能按考生编号或者姓名的字典序排。这个排序规则的设计意图是模拟真实复试名单的排序方式，总分优先，单科作为同分情况下的区分依据。
2.2 为什么“筛选”比“排序”更容易出错
排序本身不难，结构体加比较函数就能搞定。但“筛选”这个动作意味着你要先做一轮过滤，把不合格的人剔除掉，然后再对剩下的人排序。这里有两个常见的坑。
第一个坑是过滤条件写错。比如把“单科全部过线”写成了“至少有一门过线”，或者把“总分不低于国家线”写成了“总分高于国家线”。别小看这个“不低于”和“高于”的区别，边界值上差一分就是天壤之别。我在帮学生检查代码的时候，至少有三成的人在这里翻车。
第二个坑是过滤和排序的顺序搞反。有人先把所有人排序，然后再从头到尾检查谁合格，输出合格的人。这样做在结果上通常没问题，但如果题目要求输出不合格考生的信息或者统计不合格人数，顺序反了就会导致逻辑混乱。更稳妥的做法永远是先过滤出一个合格列表，再对这个列表排序。
注意：题目中如果出现了“不低于”“不少于”“至少”这类词，一定要在代码里用大于等于（>=）来实现，不要凭感觉写成大于（>）。这是最容易被忽略的失分点。
2.3 多关键字排序的比较函数怎么写才稳
多关键字排序的核心是比较函数的写法。以C++为例，如果用一个结构体存储考生信息，比较函数需要按优先级依次比较。常见的写法是：
struct Student { string id; int total; int single1; int single2; }; bool cmp(const Student &a, const Student &b) { if (a.total != b.total) return a.total > b.total; if (a.single1 != b.single1) return a.single1 > b.single1; if (a.single2 != b.single2) return a.single2 > b.single2; return a.id < b.id; }这个写法看起来简单，但有几个细节值得说。第一，每一层比较都要判断“不相等”才进入下一层，如果直接写return a.total > b.total然后接着写下一行，后面的比较永远不会执行。第二，最后的return a.id < b.id是兜底规则，保证排序的确定性，避免出现相同元素顺序不稳定的问题。第三，比较函数的参数要用常量引用，避免拷贝开销，这在数据量大的时候能省不少时间。
如果你用的是Python，排序逻辑会更简洁，可以用元组比较或者functools.cmp_to_key。但要注意Python的排序是稳定的，如果你不指定完整的比较规则，相同元素的相对顺序会保持原样，这在某些题目里可能不符合要求。
3. 完整实操流程与代码实现
3.1 输入解析与数据结构设计
假设题目的输入格式是这样的：第一行给出三个整数，分别表示考生人数N、国家线总分S、单科线D。接下来N行，每行给出一个考生的信息，包括考生编号、总分、单科一成绩、单科二成绩。我们需要输出进入复试的考生编号，按照规定的排序规则排列。
数据结构的设计直接决定了后续代码的简洁程度。我推荐用一个结构体或者类来封装每个考生的信息，而不是用多个平行数组。平行数组在排序的时候需要同时交换多个数组的元素，非常容易出错。结构体排序只需要交换结构体本身，逻辑清晰得多。
struct Candidate { string id; int totalScore; int score1; int score2; bool isQualified; };这里我多加了一个isQualified字段，用来标记这个考生是否通过了筛选。这样做的好处是可以在读入数据的时候就完成筛选判断，后续只需要对合格的考生排序输出。当然你也可以选择在排序前再过滤，两种方式都可以，但提前标记能让代码结构更清楚。
读入数据的时候要注意，考生编号可能是字符串也可能是整数。如果是字符串，排序的时候按字典序比较；如果是整数，按数值大小比较。这两种比较结果在某些情况下是不一样的，比如字符串比较中“10”会排在“9”前面，而数值比较中9小于10。题目如果没有明确说明，通常默认按字符串字典序处理，因为考生编号往往包含字母或者前导零。
3.2 筛选条件的代码实现与边界测试
筛选条件的代码实现看起来简单，但边界测试一定要做足。我通常会构造以下几组测试数据来验证筛选逻辑：
| 测试场景 | 总分 | 单科一 | 单科二 | 国家线 | 单科线 | 预期结果 |
|---|---|---|---|---|---|---|
| 全部达标 | 350 | 60 | 60 | 300 | 50 | 合格 |
| 总分刚好压线 | 300 | 60 | 60 | 300 | 50 | 合格 |
| 总分差一分 | 299 | 60 | 60 | 300 | 50 | 不合格 |
| 单科刚好压线 | 350 | 50 | 50 | 300 | 50 | 合格 |
| 单科差一分 | 350 | 49 | 60 | 300 | 50 | 不合格 |
| 两科都差一分 | 350 | 49 | 49 | 300 | 50 | 不合格 |
这六组数据覆盖了总分和单科的边界情况。实测下来，最容易出错的是“刚好压线”的情况，很多人会写成严格大于导致压线考生被误杀。另一个容易忽略的是两科都不达标的情况，虽然结果都是不合格，但如果代码里用了短路逻辑，可能只会检查第一科就返回，虽然结果正确但逻辑上不够严谨。
bool checkQualified(int total, int s1, int s2, int lineTotal, int lineSingle) { if (total < lineTotal) return false; if (s1 < lineSingle) return false; if (s2 < lineSingle) return false; return true; }这段代码用了三个独立的if判断，而不是用逻辑与连接成一个长表达式。这样做的好处是调试的时候可以清楚地看到是哪一项不达标，而且避免了短路求值带来的潜在问题。虽然代码行数多了一点，但可读性和可维护性都更好。
3.3 排序输出与格式化细节
排序完成后，输出格式也是容易丢分的地方。常见的输出要求是每行一个考生编号，或者用空格分隔在一行输出。如果题目要求输出不合格考生的信息，还要注意区分合格与不合格的输出格式。
我遇到过一种情况：题目要求先输出合格人数，再输出合格考生的编号，最后输出不合格人数和不合格考生的编号。这种多段输出的题目，一定要仔细读清楚每一段的格式要求，包括是否有空行、是否要输出表头、编号之间用什么分隔。这些细节看起来琐碎，但阅卷的时候都是按点给分的。
// 假设已经完成了筛选和排序 cout << qualifiedList.size() << endl; for (const auto &c : qualifiedList) { cout << c.id << endl; }如果题目要求在同一行输出所有编号，那就把endl换成空格，最后一个编号后面不要多输出空格。这个“最后一个元素后面不加分隔符”的细节，在在线评测系统中经常成为Presentation Error的元凶。
提示：在线评测系统对输出格式的容忍度很低，多一个空格、少一个换行都可能被判错。建议在本地测试的时候用diff工具对比输出，或者把输出重定向到文件后仔细检查。
4. 常见问题与排查技巧实录
4.1 排序结果不稳定导致的顺序错乱
排序结果不稳定是这道题的高频问题。所谓不稳定，是指当两个考生的所有比较关键字都相同时，他们的相对顺序在排序后发生了变化。在C++的std::sort中，如果比较函数没有覆盖所有情况，相同元素的顺序是不确定的。虽然题目通常不会考察这种极端情况，但如果你在比较函数里漏掉了某个关键字，就可能出现“看起来排对了但实际顺序不对”的情况。
排查方法很简单：构造一组所有关键字都相同的测试数据，运行排序后检查输出顺序是否和输入顺序一致。如果不一致，说明比较函数缺少兜底规则。补上按考生编号或者输入顺序的比较即可。
4.2 单科线判断中的“或”与“与”混淆
这是逻辑错误里最常见的一种。题目要求“每一门单科都过线”，翻译成代码应该是“如果有一门没过线就不合格”，也就是if (s1 < line || s2 < line) return false;。但有人会写成if (s1 < line && s2 < line) return false;，这就变成了“两门都没过线才不合格”，一门没过线反而合格了。这种错误在逻辑上很隐蔽，因为代码能跑通，结果却是错的。
排查方法：用前面提到的边界测试数据跑一遍，重点看“单科一差一分、单科二达标”这种情况是否被正确判定为不合格。如果判定为合格，那就是“与”“或”写反了。
4.3 数据量较大时的性能问题
虽然复试筛选这道题的数据量通常不大，但有些版本的题目会给出上万条考生记录。这时候如果排序的比较函数写得不够高效，或者用了低效的字符串比较，可能会导致超时。我实测过，在数据量达到十万级别的时候，字符串比较的开销会明显上升。
优化思路有两个：一是如果考生编号是纯数字，可以转成整数比较，速度会快很多；二是如果比较函数里有多层判断，把最可能区分出结果的条件放在最前面，减少后续比较的次数。比如总分通常分布比较分散，先比总分能快速区分大部分考生。
| 问题现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 压线考生被误判 | 用了严格大于/小于 | 构造压线测试数据 | 改为大于等于/小于等于 |
| 排序顺序不对 | 比较函数缺少兜底规则 | 构造全同数据测试 | 补上编号或输入序比较 |
| 单科判断错误 | “与”“或”写反 | 单科一差一分测试 | 改为任一科不达标即淘汰 |
| 输出格式错误 | 多余空格或换行 | 用diff对比标准输出 | 严格控制分隔符 |
| 大数据超时 | 字符串比较开销大 | 增大数据量测试 | 转整数比较或优化比较顺序 |
4.4 独家避坑技巧：先写测试再写代码
我带学生做这道题的时候，最常给的建议是“先把测试数据写好，再动手写代码”。具体做法是：在纸上或者文本文件里列出五到六组输入和对应的期望输出，覆盖正常情况、边界情况、极端情况。然后写代码的时候，每完成一个模块就用这些数据验证一次。
这样做的好处是，你不需要等到全部写完才发现逻辑错了。筛选模块写完就测筛选，排序模块写完就测排序，最后再测整体流程。这种增量式的开发方式在算法题里特别有效，因为算法题的模块划分通常很清晰，每个模块都可以独立验证。
另一个技巧是“打印中间结果”。在筛选完成后，先把合格列表打印出来看看人数和内容对不对；排序完成后再打印一次看看顺序对不对。虽然最终提交的代码不能有这些调试输出，但在本地排查问题的时候，这是最快定位错误位置的方法。
5. 从这道题延伸出的通用解题框架
5.1 多条件筛选类题目的通用模板
做完这道题之后，我总结了一个多条件筛选类题目的通用解题框架，适用于大多数类似的场景。这个框架分为四步：定义数据结构、实现筛选函数、实现排序函数、处理输出格式。
定义数据结构的时候，把每个待处理对象的所有属性都封装进去，包括用于筛选的属性和用于排序的属性。筛选函数接收一个对象，返回布尔值表示是否通过。排序函数接收两个对象，返回比较结果。输出函数根据题目要求格式化输出。
这个框架的好处是职责分离，每个函数只做一件事，调试的时候可以单独测试每个函数。而且这个框架可以直接套用到其他类似的题目上，比如奖学金评定、员工绩效考核、商品筛选排序等等。
5.2 边界条件检查清单
每次做完这类题目，我都会用下面这个清单过一遍，确保没有遗漏：
- 筛选条件的边界值是否用了正确的比较运算符
- 多个筛选条件之间的逻辑关系是“与”还是“或”
- 排序比较函数是否覆盖了所有关键字
- 排序比较函数是否有兜底规则保证确定性
- 输出格式是否与题目要求完全一致
- 空结果（没有人合格）时输出是否正确
- 全部合格时输出是否正确
- 数据量较大时是否可能超时
这个清单看起来简单，但每次过一遍都能发现一两个之前没注意到的问题。尤其是空结果和全部合格这两种极端情况，很多人写代码的时候只考虑了中间情况，极端情况直接崩溃。
5.3 从解题到实际应用的思维迁移
这道题虽然是一道算法题，但它背后的思维模式在实际工作中非常有用。比如做数据分析的时候，经常需要按照多个条件筛选数据，然后按照多个维度排序展示。再比如做招聘系统的时候，需要根据学历、经验、技能等多个条件筛选简历，然后按照综合评分排序。
核心思维是一样的：先明确筛选规则，再明确排序规则，然后实现筛选和排序，最后处理展示格式。把这四个步骤拆开，每一步都做扎实，整个系统就不会出大问题。我在实际项目中处理类似需求的时候，基本上就是套用这个思路，先和需求方确认规则，再写代码实现，最后用测试数据验证。
提示：实际工作中的筛选规则往往比题目复杂得多，可能涉及加权计算、多轮筛选、动态调整权重等等。但万变不离其宗，先把基础的单轮筛选和多关键字排序做扎实，复杂的规则只是在此基础上叠加而已。
6. 我个人在实际操作中的体会
这道题我前前后后做过不下十遍，每次带学生的时候都会重新做一遍。最大的体会是：规则理解比代码实现重要得多。很多人拿到题目就开始写代码，写到一半发现规则理解错了，推倒重来。我现在的习惯是，拿到题目先花五分钟把规则用大白话复述一遍，确认自己理解的和题目要求的一致，然后再动手。
另一个体会是，测试数据要覆盖边界。我见过太多人代码写得漂漂亮亮，结果在压线数据上翻车。后来我养成了一个习惯，每道题至少构造三组边界数据：刚好达标、刚好不达标、以及多个条件同时处于边界的情况。这三组数据能过，基本就不会有大问题了。
最后分享一个小技巧：如果你在在线评测系统上提交后一直提示Wrong Answer，但自己怎么测都测不出问题，可以试试把输出格式改一改。比如把空格改成换行，或者把换行改成空格，有时候就是这种看起来无关紧要的格式问题导致的。我遇到过好几次这种情况，排查了半天逻辑，最后发现是输出格式不对。
