PTA L1-049 天梯赛座位分配是我印象里特别适合拿来练习“模拟”的一道题。它的代码量不长思路一讲就懂但真正提交时第一次能拿到满分的人并不多。原因很简单题目把分配座位的过程描述得越贴近现实落到程序里需要处理的边界就越多。这篇文章就以这道题为例完整拆解规则、模拟过程、完整代码和常见坑给正在刷团体程序设计天梯赛题单的同学做参考。如果你刚接触这类“规则模拟”题目可能会觉得它不如那些算法题有逼格但恰恰是这种题最能暴露代码基本功。状态记录、循环终止、输出格式任何一个细节没处理好评测结果就是一片红色。接下来我按照自己的理解把这道题从规则到代码完整过一遍。1. 题目到底在考什么——规则还原与需求拆解1.1 天梯赛为什么非要“隔座”团体程序设计天梯赛的参赛队伍来自不同学校同一个学校的选手通常希望坐在一起方便沟通但竞赛规则又明确要求同一个学校的队员不能坐相邻座位。这个需求在现实里很好理解避免同伴之间交头接耳保证比赛公平。这道题把座位分配规则抽象成了这样一句话所有参赛学校按编号顺序依次分配座位每个学校有若干支队伍每队三人。如果处理到某个时刻只剩下一个学校还有队员没有分配那么这个学校每继续分到下一个座位之前都要先空出一个座位防止该校前后两个队员坐到相邻位置。这个“只剩一个学校就空一格”的规则就是整道题唯一的难点。你把它理解成什么我的理解是多所学校同时竞争座位的阶段每个学校天然被其他学校隔开而最后只剩一个学校时没有别人帮它“隔开”了只能自己手动跳过一个座位号。1.2 输入输出到底长什么样先看输入格式。第一行给一个正整数 N表示参赛学校数量。第二行给出 N 个正整数第 i 个数表示第 i 个学校的队伍数量。因为每支队伍固定 3 人所以第 i 个学校实际参赛人数是 M[i] * 3。输出格式才是很多人的噩梦。需要按照学校编号从小到大输出每个学校占若干行每个学校每个队伍占一行一行内输出该队伍三名队员的座位号用空格分隔行尾不能有空格。不同学校之间要输出一个空行隔开。我用一个例子直观感受一下。假设输入3 2 1 1意味着学校 1 有 2 支队伍共 6 人学校 2 有 1 支队伍共 3 人学校 3 有 1 支队伍共 3 人。最终输出应该是1 4 7 10 12 14 2 5 8 3 6 9注意第一行和第二行之间是空行这代表学校 1 的两个队伍之间的换行而第二个单位和第三单位之间那个空行是学校间的分隔。如果你把空行位置弄错或者行尾多了空格评测系统会直接报“格式错误”。1.3 为什么这道题被称为“模拟题”所谓模拟题就是不需要你设计什么高深算法核心任务就是把现实规则一步一步翻译成代码。L1-049 的难点在于这个翻译过程不能有歧义任何一个边界条件没有照顾到结果就会偏离真实场景。具体来说容易出错的点集中在三处。第一状态记录你至少要知道每个学校还剩多少人没分配第二循环终止所有学校的有效队员都分配完成后循环必须结束第三输出格式每行 3 个座位号、行尾不能有空格、学校之间要有空行。这三个问题解决了整道题就解决了八成功力。2. 核心思路把自己当成发座位的工作人员2.1 一个座位一个座位发的朴素模型我先放下代码讲一个接地气的类比。假设你是比赛现场的引导员手里有一沓从 1 开始编号的座位票。你按照学校编号从 1 到 N 挨个叫名字叫到一个学校就发一张当前编号最小的票然后把这张票记录下来再叫下一个学校。每个学校剩的人被叫完了你就不叫它了。等所有学校的人都拿到票分配结束。这个场景翻译成程序就是一个循环套循环的结构外层是一个“轮次”的持续过程内层是“从学校 1 到学校 N 挨个检查”。每一轮里只要某个学校还有人没分配就给它发一张票。2.2 关键判断什么时候需要跳过座位现在回到那个“隔座”问题。在多个学校同时还有人时座位号自然被不同学校交叉占用所以相同学校的队员之间必然夹着别人不需要额外处理。真正需要处理的是最后那个“孤家寡人”。举个例子A 校和 B 校比赛人数不同。前面几轮大家交叉入座等到 B 校所有人都分配完了只剩 A 校还有 4 个队员没入座。上一次 A 校队员坐的是 10 号座位如果这次直接分配 11 号那 A 校这两名队员就坐到了相邻座位违反了规则。所以正确操作是先把 11 号跳过让 A 校下一个队员坐 12 号之后再次轮到 A 校时再跳过 13 号坐 14 号。这也解释了为什么很多同学第一次写出来的代码样例能过一提交就错。因为样例里往往最后一个学校人数多结构比较规整但你自己构造一个“最后一个学校人数少且分散”的用例时不跳座的问题就暴露了。2.3 用 last 变量判断“只剩一校”的巧妙之处那么代码里怎么判断“当前只剩一个学校有人”呢最简单的方案是维护一个计数器每轮统计还有剩余人数的学校数量等于 1 就跳座。这个思路没错但实现起来要额外维护变量。还有一种更隐蔽也更省事的写法记录上一次分到座位的是哪个学校用last变量保存。如果本次轮询时发现某个学校还有剩余人数而且last刚好等于这个学校说明上一个拿到座位的人和本次拿到座位的人来自同一所学校。而在按编号顺序轮转的规则下这种情况只会发生在其他学校都已经分配完毕的时候。为什么因为只要还有其他学校有人每轮轮询一定会在中间插进其他学校的人上一次不可能连续是同一个学校。所以“上一次分配学校 本次分配学校”这个条件本质上就等价于“只剩这一个学校了”。这个条件一旦成立就先让座位号加一把这个空座跳过去。3. C 完整实现与关键代码逐段拆解3.1 完整可提交代码我直接给出一份能过题的核心代码代码部分用 C 实现。这套写法比较简洁也比较好理解。#include bits/stdc.h using namespace std; const int MAXN 105; int n; int teams[MAXN]; // 每个学校的队伍数 int rest[MAXN]; // 每个学校剩余未分配人数 vectorint seat[MAXN]; // 第 i 个学校拿到的座位号列表 int main() { scanf(%d, n); int total 0; for (int i 0; i n; i) { scanf(%d, teams[i]); rest[i] teams[i] * 3; total rest[i]; } int cur 1; // 当前可用的座位号 int last -1; // 上一次分配到座位的学校编号-1 表示还没有分配过 while (total 0) { for (int i 0; i n; i) { if (rest[i] 0) { continue; } if (last i) { cur; } seat[i].push_back(cur); cur; rest[i]--; total--; last i; } } for (int i 0; i n; i) { int idx 0; int teamCount teams[i]; for (int j 0; j teamCount; j) { for (int k 0; k 3; k) { if (k) { printf( ); } printf(%d, seat[i][idx]); } printf(\n); } if (i ! n - 1) { printf(\n); } } return 0; }这段代码的核心是while (total 0)加for (int i 0; i n; i)的双重循环。外层循环保证只要还有人没分到座位就继续整个轮询过程内层循环则模拟引导员从学校 1 问到学校 N 的过程。3.2 数据结构vector 存座位号我选择vectorint seat[MAXN]来存储每个学校拿到的全部座位号。这个选择有几个好处。第一不同学校的人数不同用vector就不需要事先算最大容量分配多少存多少代码可读性更高。第二题目要求每个学校按队伍输出每队 3 人而seat[i]中记录的正好是按分配顺序排列的队员座位号只要把seat[i]按下标每 3 个切一段输出即可。第三vector的push_back操作天然支持动态追加让分配过程的代码和真实发座位的动作一一对应。如果非要用固定二维数组也不是不行但你得额外开一个int seat[105][305]这样的结构还得用一个int count[105]去记录每个学校当前已经存了多少个座位。这样写当然没问题但对初学者来说多维护一套计数索引出错概率会上升。3.3 三层循环输出输出部分看起来简单实际上有三个需要小心的位置。最外层循环按学校编号输出编号从 0 到 n-1。中间层循环按队伍数量输出队伍数量由输入时的teams[i]决定。最内层循环固定输出 3 个座位号因为每队固定 3 人。在中间层循环里我使用了一个idx指针指向seat[i]当前应该取出的座位位置。每输出一个座位号idx就加 1。这样seat[i]中存的 6 个座位号第 0 到第 2 个是队伍 1 的三名队员第 3 到第 5 个是队伍 2 的三名队员以此类推。行尾空格的控制方式是在每个数字前判断是否为该行的第一个数字是就不输出空格不是就输出一个空格。这种“先空格后数字”的写法比“数字后空格再判断末尾”要安全得多可以彻底避免行尾多一个空格的尴尬。3.4 手算样例验证分配过程我拿前面那个样例再推演一遍方便你对照代码看过程。N3teams 数组是 2、1、1所以 rest 数组初始是 6、3、3total 初始是 12。第一轮循环学校 0 剩余 6 人last 是 -1 不等于 0直接分配座位 1last 更新为 0。学校 1 剩余 3 人last 是 0 不等于 1直接分配座位 2last 更新为 1。学校 2 剩余 3 人last 是 1 不等于 2直接分配座位 3last 更新为 2。第二轮循环学校 0 分配座位 4学校 1 分配座位 5学校 2 分配座位 6。这时 rest 数组变成了 4、1、1total 还剩 6。第三轮循环开始前last 是 2。学校 0 的 last 不等于 0分配座位 7。学校 1 的 last 不等于 1分配座位 8。学校 2 的 last 不等于 2分配座位 9。此时 rest 数组变成了 3、0、0total 还剩 3。第四轮循环学校 0 的 last 当前是 2不等于 0所以正常分配座位 10。之后 rest[0] 变成 2total 还剩 2last 更新为 0。后面学校 1 和学校 2 都已经没人了直接跳过。第五轮循环学校 0 剩余 2 人last 是 0等于 0触发空座逻辑cur 先加 1把 11 空出来然后分配 12。接着 rest[0] 变 1total 变 1last 仍是 0。第六轮循环学校 0 剩余 1 人last 还是 0继续触发空座逻辑cur 先加 1把 13 空出来然后分配 14。分配完 total 变 0循环结束。于是学校 0 的座位列表是 1、4、7、10、12、14。输出时队伍 1 是“1 4 7”队伍 2 是“10 12 14”。学校 1 是 2、5、8学校 2 是 3、6、9。你可以看到最后只剩学校 0 时10 和 12 之间隔了 1112 和 14 之间隔了 13完全满足同一学校不相邻的要求。4. 踩坑实录那些让我卡了很久的细节4.1 last 变量到底记录的是什么这个坑我相信很多人踩过。last记录的应该是“上一次真正分到座位的学校编号”而不是“上一次遍历到哪个学校”。代码里last i这一行只能放在成功分配座位之后不能放在continue之外。如果你一时手滑把last i写在了for循环的末尾也就是不管rest[i]是否为 0 都执行那就会导致last总是被最后一个非空学校覆盖。举个例子假设学校 0 没人了学校 1 还有人遍历到学校 0 时 rest 为 0 跳过了但因为last i放在了循环尾部last 可能被更新成 0。这样之后判断last i时就会出错要么过度跳座要么漏掉跳座。正确写法是只在seat[i].push_back(cur); rest[i]--; total--;之后才更新last i。也就是说last要反映真实发座动作的接收方。4.2 空座的位置先跳跃还是后跳跃if (last i) cur;必须放在取座位号之前。很多同学会写成这样if (last i) { seat[i].push_back(cur); cur 2; }这种写法的错误在于当需要跳跃时当前这个座位号本身还是被同一学校的上一个人占用了没有任何间隔。比如 last 为 0cur 是 11本来应该空出 11把 12 给学校 0但这种写法会把 11 直接给学校 0等于没隔开然后 cur 从 13 开始下一轮反而多跳了一个。所以直觉上“先让座位号前进一位再取号”才是对的。这个顺序非常关键可以用一句话记跳跃发生在当前学校“坐下”之前而不是之后。4.3 输出格式行尾空格与学校间空行这道题对输出格式要求相当严格。如果你的代码在行尾多输出一个空格PTA 通常会报“Presentation Error”扣分但不至于全错。如果是空行数量不对那就更麻烦可能直接算你答案错误。我习惯的做法是“每行开始前判断是否需要空格”也就是先输出第一个数字之后每个数字前补一个空格。这样不会出现行尾空格。学校之间的空行我建议在输出完整所学校的所有队伍后再补一个回车。也就是说当i ! n - 1时额外输出一个\n。还有一点最后一个学校的最后一行末尾要不要换行其实不影响通过。但我个人会保留最后的换行这样和其他题目的输出习惯保持一致。4.4 “只有一个学校”要不要特判这个问题经常出现在讨论区。很多人害怕 N1 时规则不好处理于是单独写了一堆特判。其实使用last i判断后N1 的情况是天然兼容的。试想 N1学校 0 有 6 人。第一次循环last 是 -1不等于 0所以正常分配座位 1last 变成 0。第二次循环last 是 0等于 0触发跳座分配座位 3。之后每轮都是“先跳一格再坐人”最终座位号是 1、3、5、7、9、11。这个结果完全符合只有一个学校时每个队员之间需要隔开一个座位的规则。所以不需要额外写“if (n 1)”这种特殊分支。加了反而容易把逻辑搞乱。4.5 死循环排查如果 while 循环条件写成while (true)而内部又没有及时更新total就可能出现死循环。常见错误是把total--漏写在某条分支里。我用的是while (total 0)并且保证每次分配座位后total--所以一旦 total 归零外层循环立刻退出。调试时如果发现程序跑不完优先检查rest[i]--、total--和last i这三行是否都执行到了。4.6 常见问题速查表现象可能原因解决办法最后一个学校相邻座位没有隔开last i判断写错或cur放在取号之后把跳跃逻辑移到取号之前输出后比预期多了一堆数字没有控制好 total 循环次数rest 更新遗漏确认 rest[i]-- 和 total-- 成对出现一提交就是格式错误行尾空格或学校间空行不对使用“先空格后数字”输出学校间单独补空行多个学校时也有相邻同校座位可能是重复分配了座位last 更新位置错误检查 last 是否只在分配座位后更新5. 从这道题看模拟题的通用套路5.1 模拟题的三件套状态变量 主循环 边界刷过一定量的题之后你会发现模拟题几乎都长一个样给你一套现实规则让你用程序完整走一遍过程。无论题目伪装成“排队叫号”“轮转调度”还是“天梯赛座位”底层结构都离不开三样东西。第一状态变量。你必须清楚整个过程有哪些需要持续跟踪的数据。在这道题里状态变量是rest[]、total和last。rest[]记录每个学校剩余人数total记录所有学校剩余总人数last记录上一次分配给了谁。少一个状态模拟就无法继续。第二主循环。主循环负责让时间轴前进。这里用的是“轮询所有学校”的for循环外层再用一个while判断是否还有未分配的人。很多模拟题的主循环形式不同有的是“队列直到为空”有的是“事件驱动”但本质都是让过程推进。第三边界条件。边界条件往往藏在题目的“最后只剩下一个学校”这类描述里。读题时稍微不留神等你写完代码后才发现样例过了隐藏边界却炸了。5.2 写模拟题时如何减少调试时间我的经验是不要一上来就写完整代码。先拿一个很小的输入比如 N2每队 1 人在纸上手推一遍座位号。然后拿 N1 和一个学校队伍特别多的用例分别手推一遍。确认自己理解了规则再动手写代码。写完代码后如果 WA 了不要瞎改。把 print 语句加进去在每个关键位置输出当前 cur、last、current rest。比如在分配座位前后各打一行观察 cur 是否按预期跳跃。这个过程往往能很快定位问题。另外一定要学会构造“不对称”的测试数据。所有学校人数一样时问题不容易暴露一旦有一个学校特别少或者特别多空格逻辑就会开始犯病。像 N3、M 数组为 {1, 5, 2} 这种数据就是很好的试金石。5.3 类似题型对比我在刷题时发现这类“按顺序轮转分配”的题目非常普遍。约瑟夫环是“按固定步长删人”核心是需要时刻知道当前活着的编号。它和我们这道题的区别是删除逻辑和轮询逻辑耦合在一起。L1-049 是固定按学校编号顺序访问不需要删除中间节点只需要跳过已经没人排队的学校所以更简单。银行叫号系统是“多个窗口轮流处理队列”其实是多个队列同时出队但和“多个学校轮流分配座位”的模型几乎一样。如果你以后遇到“医院分诊叫号”“多进程轮转调度”等模拟题思路完全可以复用维护每个对象的剩余需求按固定顺序轮转用状态变量记录上一个处理对象。6. 变式与扩展思考6.1 如果每队人数不是 3 人怎么办天梯赛固定每队 3 人但题目如果把“3”换成“每组 k 人”只需要把代码里的魔法数字 3 替换成变量 k。rest[i] teams[i] * k输出时内层循环从 3 改成 k其余逻辑完全不变。建议你写代码时把队伍人数先用常量或变量定义好不要到处写魔法数字。这样当题目场景变化时只改一处就能适配。这不仅是好习惯也是模拟题通用的抗变更设计。6.2 如果输出顺序变了怎么办有些类似题目不是“按队伍输出”而是直接输出每个学校的全部座位号。这时你就不需要三层循环中的“队伍”这一层直接把seat[i]从头到尾输出即可。甚至可以把输出逻辑改成直接使用seat[i].size()判断共有多少队员而不是依赖teams[i] * 3。如果题目要求座位号从 0 开始那就把cur初始改为 0其他逻辑同样不用动。所以我把分配核心逻辑和输出逻辑分离正是为了应对这类变式。6.3 如果允许同校相邻怎么简化反过来思考如果题目不要求同校隔开代码会变成什么样其实只要删掉if (last i) cur;这一行整个系统就退化为“按学校编号顺序轮询发座位谁有人就给谁发”。不再需要last变量也不需要“空座”概念。这个对比能帮你更深刻地理解last的作用它不是模拟题强加的装饰而是专门为了处理“最后剩余单校”的隔离需求而存在的状态变量。你把需求删掉状态自然也就不用维护了。我自己第一次做 L1-049 的时候其实输在了一个很小的地方我把last的更新放在了continue之后结果导致last被没有实际分到座的学校覆盖整个跳跃逻辑全部错乱。后来用一组“最后一个学校编号最小”的边界用例调试时才找到问题。那次之后我养成一个习惯任何模拟题里的状态变量我都先问自己三个问题它什么时候初始化什么时候更新什么时候影响判断把这三个问题想明白再动手写代码效率会高很多。这道题的难度不高但它很适合用来检验你对“过程模拟”的掌控力。如果你能把这段代码讲清楚把last的机制说明白那你对循环、状态、边界这三样基本功的理解已经比大多数只看题解的同学扎实了。