做 PAT 模拟题做到 A1080 的基本都是冲着“模拟题天花板”这个定位来的。30 分里带着一个“并列排名也要照单全收”的隐性规则看着是录取流程模拟实际上考的是排序、结构体设计、还有边界条件处理。我当年第一次写出满分代码的时候最深的感受不是这题算法有多难而是“读懂规则”比“写代码”更费时间。这篇文章就按我的复盘思路把 A1080 从题目拆解到代码落地、从常见踩坑到变形扩展整套讲透。1. 题目在考什么录取流程的完整拆解1.1 一眼看懂规则A1080 描述的场景很清晰有 N 个申请者、M 所学校、每个申请者最多填 K 个志愿。每所学校有固定的录取名额。每个申请者有两个成绩GE 是初试成绩GI 是复试成绩总成绩是 GE 和 GI 之和。录取流程分两步所有申请者按总成绩降序排序总成绩相同则按 GE 降序排序。按这个全局排名从高到低依次处理每个申请者的志愿从第一志愿开始只要学校还没录满就录取他如果第一志愿满了看第二志愿依次类推。题目强调了一个非常容易忽略的关键条件如果申请者的总成绩和 GE 都和当前学校最后一名录取者相同即使该校名额已经用完也必须录取该申请者。换句话说并列排名不受名额限制约束。这个条件在英文题面里用一个从句表达得比较含蓄很多考生第一次做都会漏掉导致最后两个测试点过不去。这也是 A1080 能拿到 30 分分量的原因不是考你会不会排序而是考你能否在模拟业务规则时做到滴水不漏。1.2 题目真正的难点在哪里从算法角度说A1080 没有递归、没有动态规划、没有复杂的数据结构就是“排序 一条队列依次处理 哈希表或数组记录结果”。它的难点集中在三个地方并列排名的处理不是比较分数而是比较“排名”本身。排名相同指的是总成绩和 GE 都相同缺一不可。学校的录取结果需要记录“最后一名录取者的总成绩和 GE”用于后续申请者的并列判断。一旦理解成“比较分数”在极端数据下就会出错。输出时每个学校要按申请者编号升序输出而不是按录取顺序输出。这是输出侧的隐藏要求不少人排序完直接打印录取顺序结果格式错误。另外还需要注意每个申请者只能被一所学校录取一旦录取后面的志愿作废所得录取结果要按学校分组存储。这些都是业务规则层面的细节缺一块都会出问题。1.3 适合什么基础的人看如果你是刚学完结构体和 sort 排序的初学者A1080 是一道很好的综合练习题建议先自己写一版不用管分数写完了再对照本文看漏了哪些边界。如果你已经在准备 PAT 的冲刺阶段A1080 更应该当“避坑清单”来看尤其是并列排名的处理值得单独背下来。我自己习惯把 A1080 归类为“业务模拟题”没有高级算法但考察读题、数据建模、边界验证的综合能力。工作以后做后台开发经常要处理这类“规则一堆、逻辑不复杂”的需求A1080 的训练价值其实比想象中大。2. 排序与数据结构是这类题的生命线2.1 申请者结构体怎么设计这道题所有逻辑都围绕申请者展开结构体设计直接影响代码可读性和正确性。我的设计是这样的struct Applicant { int id; // 申请者编号从 0 开始 int ge, gi; // 初试成绩、复试成绩 int total; // 总成绩 int rank; // 全局排名 vectorint choices; // 志愿学校编号按优先级从高到低 };id 必须保留因为最终输出要求学生编号按升序排列排序会打乱原始顺序没有 id 根本没法恢复。rank 字段是优化的关键排名只需要算一次后续所有并列判断都直接比较 rank 是否相等不需要反复比较 total 和 ge。也有人不单独算 rank每次比较时写一个isSameRank(a, b)函数判断条件就是a.total b.total a.ge b.ge。两种做法都可以但带上 rank 字段主逻辑会简洁很多尤其在后面处理“并列时额外录取”的规则时一行代码就能说清楚。2.2 排序规则先总成绩再初试成绩排序函数本身不难但要注意比较方向成绩高的排前面所以是降序bool cmp(const Applicant a, const Applicant b) { if (a.total ! b.total) return a.total b.total; return a.ge b.ge; }排序完成之后要立即计算全局排名。排名规则是第一名是 1如果当前申请者和前一个申请者的 total 和 ge 完全一样排名和前一个相同否则排名等于当前下标加 1假设排序后下标从 0 开始。这一步我建议单独写一个循环来处理不要和排序逻辑混在一起。排序只做排序排名是排序之后的状态计算分开写更清晰for (int i 0; i n; i) { if (i 0 apps[i].total apps[i-1].total apps[i].ge apps[i-1].ge) { apps[i].rank apps[i-1].rank; } else { apps[i].rank i 1; } }排名计算完成后所有申请者已经按录取优先级排好序。接下来就是按排名从高到低逐个处理志愿这一步不需要再排序也不需要优先队列直接一个 for 循环即可。还有些人会用 priority_queue没必要反而引入额外的复杂度。2.3 录取结果存储数组加向量最直接学校的录取名单可以用vectorint admitted[M]表示每个学校一个动态数组顺序就是录取顺序。但输出要求按学生编号升序所以输出前需要对每个学校的数组做一次排序。学校这边还需要记录每个学校当前已经录取的人数以及“最后一个录取者的排名”。我用两个数组来存int quota[M]; // 每所学校的名额 int lastRank[M]; // 每所学校最后一个录取者的排名初始化为一个很大的数 int admittedCount[M]; // 实际录取人数 vectorint admitted[M]; // 每所学校录取的申请者编号lastRank 初始化为一个很大的值比如 1000000表示“学校还没有录满、不存在最后一名”的状态。注意这个值不能初始化为 0否则所有并列判断都会错误地命中“最后一名”导致疯狂超额录取。为什么用数组而不是结构体数组来存学校信息因为学校的逻辑很简单就是“有没有名额”“最后一个录取者是谁”拆成数组写起来更直观而且排序学校的录取名单时只需要处理 vector不需要额外更新 quota 等字段。3. 模拟录取的核心流程与代码骨架3.1 主流程先全局排序再逐个处理志愿主流程是一个线性扫描。按排名排序后的申请者数组从前往后遍历。对每个申请者遍历其 choices 向量检查志愿学校是否满足录取条件for (int i 0; i n; i) { for (int j 0; j k; j) { int school apps[i].choices[j]; if (admittedCount[school] quota[school]) { admit(apps[i], school); break; } // 名额满了但并列排名也必须录取 if (apps[i].rank lastRank[school]) { admit(apps[i], school); break; } } }这段代码是整个题目的心脏。注意 if 的顺序先判断名额是否足够名额够直接录取并 break名额满了才进入并列判断。为什么不能把并列判断放前面因为如果学校名额没满无论排名是否相同本来就能录取放前面虽然结果一样但逻辑上会让人困惑而且如果 lastRank 没初始化好还会引入错误。每次录取之后更新学校的录取人数和 lastRankvoid admit(Applicant app, int school) { admitted[school].push_back(app.id); admittedCount[school]; lastRank[school] app.rank; }这里有个隐藏逻辑只有真正录取了lastRank 才更新。如果学校名额未满就录取lastRank 自然就是这个申请者的排名如果因并列而额外录取lastRank 更新为同一个排名后续仍可能继续录取同样并列的人。这是题目规则“并列均录取”的数学表达。3.2 并列排名处理核心难点的两种实现姿势并列排名的处理是这个题最值得展开的地方。我第一次写的时候想的是“如果名额满了就看这个申请者的 total 和 ge 是否等于学校最后一名录取者的 total 和 ge”代码是这样if (admittedCount[school] quota[school] || (apps[i].total lastTotal[school] apps[i].ge lastGe[school])) { admit(...); }这个写法对吗在 AC 的前提下通常是能过的因为“最后一名录取者的 total 和 ge”本质上就代表“该学校目前能接受的最低录取标准”。但问题在于你需要额外维护 lastTotal 和 lastGe 两个数组而且总成绩那个字段是用 totalGEGI还是单独再算容易搞混。我后来改成 rank 方案因为“排名相同”才是题目最本质的表达。学校的 lastRank 记录最后一名录取者的排名新申请者只要 rank 和 lastRank 相等就说明两个人 total 和 ge 完全相同这时候名额满了也要录。一行比较既贴合题面描述也避免了字段维护的麻烦。这里必须强调一个关键点并列判断用的是“是否相等”不是“是否大于或相等”。由于我们是从高排名到低排名顺序处理的新申请者的 rank 只会大于等于当前学校 lastRank不可能小于所以用等于判断是准确的。如果题目改成倒序处理比较方向才需要改变。3.3 输出格式细节按编号升序再打印所有申请者处理完毕后每个学校都有一个录取名单。题目要求按学校编号从 0 到 M-1 输出每所学校内部的学生编号按升序排列。如果某学校没有录取任何人输出一个空行。这里有一个很常见的坑直接把 admitted[school] 按录取顺序输出因为在主流程里申请者是按分数从高到低处理的编号是乱序的。比如编号 200 的学生比编号 5 的学生分数高先被录取那么 admitted[school] 里 200 在 5 前面。必须排序后再输出for (int i 0; i m; i) { sort(admitted[i].begin(), admitted[i].end()); for (int j 0; j admitted[i].size(); j) { if (j) printf( ); printf(%d, admitted[i][j]); } printf(\n); }为什么题目要这么设计因为录取是按成绩排名的而最终名单面向的是学生个人按编号升序才方便核对。这跟实际业务很像——数据库里存储顺序是业务的对外展示顺序是用户的两套逻辑。输出细节还包括编号从 0 开始还是从 1 开始取决于输入格式。A1080 的学生编号是从 0 到 N-1。有些题从 1 开始我会在结构体里统一存 0 基编号输出时再加 1这样排序和 vector 下标都不需要调整。4. 踩坑实录与常见问题排查4.1 并列名额最后一个测试点过不去的元凶PAT 的测试点里专门有一组数据是“多个申请者总分和 GE 都相同但学校名额不足”。比如某个学校只剩 1 个名额排在前面的是 3 个并列第一名的申请者三个人都填了这个学校的第一志愿。按规则三个人必须全部录取哪怕名额超了 2 个。如果你的代码只判断“名额未满”就会漏掉后两个人导致正确答案是 3 人你输出 1 人。这个测试点非常毒因为前几个测试点可能不会触发这个规则你自己试常规数据也发现不了问题。我当时就是提交了两次都挂在最后一个点才回头仔细看题面里的并列条件。解决方案就是前面代码里的apps[i].rank lastRank[school]判断没有第二招。值得注意的是这个规则还会引发连锁反应因为掉了 2 个名额后面的申请者即使分数比这三人低也会被这所学校拒绝转而看第二志愿。这些连锁逻辑只要主循环顺序正确不需要额外处理但理解它有助于你构建测试数据。4.2 志愿顺序填了就会被按顺序尝试每个申请者有 K 个志愿但题目没说这 K 个志愿一定“有效”。比如申请者只填了 1 个志愿后面全是无效学校编号或者填了重复的学校。我在第一次写时没考虑重复志愿的情况后来查了题面确认志愿是各不相同的不需要去重。但如果你在训练平台遇到变种题建议看一眼数据范围做一次去重也不难。处理志愿时一旦某志愿录取成功直接 break 跳出志愿循环不需要继续看后面的志愿。有些同学会用 flag 变量标记是否录取虽然也能过但我在代码里直接 break逻辑更简洁。注意 break 只跳出内层循环志愿循环不会影响外层申请者循环因为录取完成后这个申请者的处理就结束了。4.3 输出顺序学校内部的编号排序有个问题容易被忽略即使你排序了排序的粒度也容易搞错。每个学校自己的录取名单排序不是所有学校混在一起排序。我见过有人把 admitted 数组整体排了个序结果输出完全乱套。正确做法是循环每个学校对admitted[i]单独排序。另外输出格式里每所学校之间是换行不是空格。学校没有录取学生时输出一个空行。这个细节在样例输出里能看到但很多人容易忽略导致 Presentation Error。PAT 对空行的要求很严格多一个、少一个都不行。4.4 数据范围与复杂度不需要优化但要注意类型N 的最大值是多少我记得是 40000学校 M 最大 100志愿 K 最大 5。N 乘 K 最多 20 万次操作sort 一次 N 个元素也完全没压力。所以这个题不需要任何高级优化暴力模拟即可。但要小心两个细节第一总成绩我用ge gi不会超过 200int 完全够第二由于并列额外录取某学校的最终录取人数可能超过它的 quota这没问题题目本来就不要求最终录取人数等于 quota。如果你在输出时用admittedCount[i]去限制打印人数反而会截断正确结果。4.5 一套自测数据教你验证正确性分享一套我常用的自测数据把并列和超录情况都覆盖到6 2 2 1 0 1 0 10 10 0 1 20 20 1 0 20 20 0 1 20 20 1 0 10 10 0 0 30 30 1 1第一行6 个申请者2 所学校每人 2 个志愿。第二行是两所学校的配额学校 0 名额 1 个学校 1 名额 0 个。接着每行是一个申请者GE、GI、第一志愿、第二志愿。这里学校 1 名额为 0专门测试“空额 并列”组合。你自己跑一下如果输出里学校 1 不是空行说明逻辑有问题。这类刁钻数据比样例更能暴露问题建议练习时多构造几种组合。5. 从 A1080 延伸出去的思考模拟题的通用套路5.1 把“显式规则”和“隐式约束”分开列刷多了模拟题会发现任何业务模拟题都可以拆成两层显式规则是题目直接告诉你的比如“成绩高者优先”隐式约束是藏在描述里的比如“并列排名不受名额限制”甚至“输出按编号升序”这种格式要求。我的习惯是读题时拿支笔把规则按这两类列出来。显式规则进代码隐式约束进注释。A1080 如果只盯着显式规则写一定漏掉并列录取把隐式约束单独列出来思路会清晰很多。这个方法对 PAT 里的其他模拟题同样有效。5.2 用“状态字段”代替“重复比较”这个题里 lastRank 数组就是典型的状态字段优化。如果不维护它每次都要取学校最后一个录取者的 total 和 ge 来比较不仅代码啰嗦还容易出错。把需要反复比较的属性提前计算成状态是一种通用技巧。类似的场景还有计算排名时不重复比较 total 和 ge先算好 rank输出前先排序录取名单而不是输出时临时判断。这些都是“空间换逻辑复杂度”的小优化在竞赛里不显眼但能显著降低调试成本。5.3 如果题目改版你还能这样调整A1080 是一个很经典的“名额分配”模型实际工作中也有类似场景。如果我把题目改成这样你可以想想怎么调整每所学校不止一个最低排名而是记录多个“并列段位”的最后一人或者申请者可以选择“服从调剂”未录取时自动分配到剩余名额最多的学校再或者多个学校联合招生学生一旦被更高优先级的学校录取要从低优先级学校的名单里移除。这些问题看起来复杂本质还是“状态字段 有序处理”。比如调剂逻辑只要在处理完所有正常志愿后再来一轮未录取者按排名依次填补空额即可。A1080 教会你的不是代码而是如何把模糊的业务描述翻译成精确的算法逻辑。我个人的体会是A1080 值得在 AC 之后再重新手写一遍不参考任何代码从读题到输出完整走一遍。第二次写你会发现自己对题目规则的理解比第一次深很多尤其是并列处理第一遍是“照着规则写”第二遍才是“真正理解为什么这样写”。这种从 AC 到内化的过程比单纯刷题数量更有价值。