“天梯赛座位分配”是PTA天梯赛L2里非常经典的一道模拟题。题目看起来简单描述也不长但每年都有人被最后几行数据打崩——不是循环写错了而是没搞懂“同一学校队员不能相邻”这句话在只剩一个学校时意味着什么。这篇文章不绕弯子从题意、规则拆解、代码实现到边界样例完整复盘这道题的解法。C为主思路完全可以平移到Python、Java。1. 题目到底让你干什么1.1 输入输出长什么样先看题目的表面形式。输入第一行是学校数量N接下来N行每行一个整数表示该学校的队伍数。每支队伍固定10名队员。输出要求按学校编号从1到N每个学校先输出一行“#编号”然后把这个学校所有队员的座位号按队伍顺序输出每支队伍占一行一行10个号码。比如这样一组输入3 3 4 2对应输出是#1 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 63 65 67 69 71 73 75 77 79 #2 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 #3 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60注意这里座位号不是连续铺满的。学校2总共有40人最后一个人的座位号却是100原因就是座位中间出现了空位这些空位是为了满足“同校不相邻”的规则。1.2 这道题考的是模拟基本功天梯赛L2级别的题目很多选手会默认“L2就该上数据结构或图论”但座位分配这道题完全不是。它不考树、不考图、不考复杂算法考的就是你能不能把一段文字规则翻译成严谨的流程。翻译出来的核心规则是所有座位按号码从小到大依次安排人多个学校都有剩余队员时各学校按编号从小到大循环轮流坐当场上只剩一个学校还有人没坐下时如果上一个座位坐的恰好也是这个学校的人就必须空出一个座位再坐下一个人。所以算法层面就是纯模拟。难的不是算法而是状态判断——什么时候需要让座位号跳一格。一旦这个判断写错样例可能碰巧能过但极端数据会立刻暴露问题。2. 相邻规则的本质从“多校交替”到“单校隔位”2.1 多校并存时为什么不用额外处理当至少两个学校还有剩余队员时规则其实很宽松按编号循环分配即可。为什么不用管“同校不相邻”因为“按编号循环分配”本身就保证了相邻座位必然属于两个不同学校。考虑两个学校A和B都还有人上一轮A拿到座位xB拿到x1下一轮也是先给A发x2再给B发x3。这样A的队员永远被B的队员隔开不可能出现两个A坐在一起的情况。三个及以上学校也一样循环轮转天然规避了同校相邻。所以多校阶段代码只需要做一件事每一轮从头到尾扫一遍学校谁还有剩余就给谁发一个座位号。2.2 只剩一所学校时隔位到底隔几个当只剩一所学校还有剩余队员时循环轮转就失效了因为每一轮都只有这一个学校能领到座位如果连续发放同校队员必然相邻。解决办法是在“上一个座位归属”也是这个学校的情况下先把当前座位号加1表示这个座位空出来不用然后再把加1之后的座位号分配给该校队员。举个例子。某校最后十几个队员要入场上一名队员坐在80号。此时80号属于该校如果继续发81号81号和80号就是相邻座位违反了规则。所以先让座位号跳到82号再把82号发出去。下一次同理84、86、88……中间的空座位号全部浪费掉。这里有个容易误解的细节隔位不等于“座位号固定加2”。只有在上一名队员确实是当前学校时才需要先空一位。如果上一名队员是其他学校或者这是全场第一个座位就不需要空。这也是为什么很多初写这道题的人会把逻辑写成“只剩一个学校就pos加2”结果在边界数据上多跳了一位。2.3 last变量间隔逻辑的“记忆锚点”要判断“上一个人是不是当前学校”就必须记录上一个人的学校编号。这个变量通常命名为last初始值可以设为-1表示还没有任何人坐过。last的更新逻辑非常简单每次给某个学校分配一个座位就把last更新为这个学校的编号。多校交替阶段last会频繁变化单校阶段last会固定成那唯一一个还在排队的学校。有了last隔位条件就是一句直白的判断if (只剩一个学校且这个学校 last) { pos; // 空出一个座位 }3. 主循环设计先统计再分配避免一起判断3.1 为什么用剩余人数数组而不是已分配数组每个学校有初始人数total[i]这部分来自输入队伍数乘10。模拟过程中需要一个数组记录该校还有多少人没座位常用的做法是开一个rem数组初始等于total每分配一个座位就减1。有的同学喜欢用“已分配人数used[i]”来判断“used[i] total[i]”这也能用。但用剩余人数的好处是直观统计“还有几个学校剩余”时直接遍历rem数组数一下大于0的个数就行不用做减法。3.2 while for 的框架整个模拟可以缩成一个while循环循环条件很简单还有任何人没分配完。每轮进入while之后先做一次全量统计确认当前剩余学校数量。这一步非常关键它把问题分成了两个清晰的场景场景一剩余学校数量大于1执行普通轮转分配。场景二剩余学校数量等于1执行隔位分配。对应伪代码如下while (总剩余人数 0) { 统计剩余学校数量 cnt 和唯一剩余学校的编号 only; if (cnt 1) { if (last only) pos; 给 only 学校分配 pos; pos; last only; } else { for (int i 0; i n; i) { if (rem[i] 0) { 给 i 学校分配 pos; pos; last i; 总剩余人数--; } } } }这个“先统计、再分支”的结构比在for循环内部边分配边判断要清晰得多。你不用担心“当前学校分配完之后场上是不是只剩它了”因为全局状态已经在每一轮开始前确认过了。3.3 三种状态下的座位号推进把座位号的推进方式整理成一张状态表会很直观场景是否隔位pos变化方式多校剩余按编号普通分配不需要pos加1单校剩余且上一名队员不是该校不需要pos加1单校剩余且上一名队员就是该校需要先空一位pos先加1分配给队员后再加1注意最后一种情况pos实际发生了两次自增。第一次自增产生空位第二次自增产生分配给队员后的下一个待用座位号。很多错误实现只写了一次自增或者直接写“pos 2”在特定输入下会把第一个不需要隔位的位置也跳过最后答案整个错位。4. 完整C实现与手工验证4.1 可AC的参考代码下面是完整可运行的C实现关键逻辑都有注释#include bits/stdc.h using namespace std; const int TEAM_SIZE 10; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint total(n), rem(n); int sum 0; for (int i 0; i n; i) { int teams; cin teams; total[i] teams * TEAM_SIZE; rem[i] total[i]; sum rem[i]; } vectorvectorint seat(n); int pos 1; int last -1; while (sum 0) { int cnt 0; int only -1; for (int i 0; i n; i) { if (rem[i] 0) { cnt; only i; } } if (cnt 1) { int i only; if (last i) pos; seat[i].push_back(pos); rem[i]--; pos; last i; sum--; } else { for (int i 0; i n; i) { if (rem[i] 0) { seat[i].push_back(pos); rem[i]--; pos; last i; sum--; } } } } for (int i 0; i n; i) { cout # i 1 \n; for (int j 0; j (int)seat[i].size(); j) { if (j % TEAM_SIZE ! 0) cout ; cout seat[i][j]; if (j % TEAM_SIZE TEAM_SIZE - 1) cout \n; } } return 0; }这段代码的空间复杂度是O(总人数)因为每个学校开了一个vector存座位号。时间复杂度方面while循环每处理一轮要扫描一遍学校列表总人数不超过10万量级扫描代价完全可以接受。4.2 用一组样例把分配过程走一遍拿上面那组输入来验证核心逻辑。三个学校初始人数分别是30、40、20。第一阶段三校都有剩余每轮按1、2、3的顺序各发一个座位第1轮学校1拿1学校2拿2学校3拿3。第2轮学校1拿4学校2拿5学校3拿6。第20轮结束时学校3的20人全部拿到座位最后一个座位号是60。此时剩余学校有学校1和学校2。学校1还剩10人学校2还剩20人。第21轮开始进入双校交替第21轮学校1拿61学校2拿62。第30轮学校1拿79学校2拿80。第30轮结束后学校1的30人全部到位学校2还剩10人。最后阶段只剩学校2上一名队员坐在80号同样属于学校2所以必须空出81号直接发82号给学校2。之后每一次发座前都要先空一位于是学校2剩余队员座位号依次是82、84、86、88、90、92、94、96、98、100。对应输出就是文章开头列出的那个表和我手动推演完全一致。4.3 极端边界单学校与双学校悬殊再验证两个极端样例。第一个只有一个学校1支队伍。初始10人没有任何其他学校。第一次分配时last为-1不隔位座位号1给出去。第二次开始last等于学校1所以每次都要先空一位最终座位号是1、3、5、7、9、11、13、15、17、19。后面9个座位全部隔位。这符合题意一个学校自己坐全场也必须满足同校不相邻。第二个两个学校学校1有1支队伍学校2有100支队伍。第一阶段双校交替学校1拿1学校2拿2学校1拿3学校2拿4……一直交替到第10轮学校1拿完第10个座位也就是19号座位这里要仔细算双校交替时每轮学校1拿一个、学校2拿一个。第k轮学校1拿2k-1学校2拿2k。第10轮学校1拿19学校2拿20。此时学校1全部坐完学校2还剩990人。接下来学校2开始进入单校隔位阶段因为上一名队员是学校2且只剩学校2第一个剩余座位要从22开始然后24、26……后续所有座位都是隔一个空位。这个边界能有效检验“last记录”是否正确。如果错误地写成“只剩一个学校就无条件先跳一位”第二个例子会变成学校2从21开始看似没大问题但单学校例子中第一个座位就会从2开始立刻被卡住。5. 实战踩坑记录三个最容易错的地方5.1 坑一忘记队伍人数要乘10这是最蠢但最常见的错误。输入给的是“队伍数”不是“队员数”。一支队伍10个人所以总人数是队伍数乘以10。有的选手把队伍数直接当成人数来模拟样例数据如果是几支队伍输出规模会差一个量级肉眼一眼就能看出来不对。但要是恰好题目给的队伍数比较小输出现象不明显这种错反而难排查。5.2 坑二把“隔一位”写成“每次跳两位”我在写第一版时直接把单校阶段的逻辑写成了pos 2; seat[i].push_back(pos);表面看只剩一个学校时每发一个座位跳两个号似乎就是隔位。真正跑起来才发现第一次进入单校阶段时根本不该跳。因为上一名队员很可能是其他学校的人不是当前这个唯一剩余学校的人。只有确认上一名队员和当前学校相同才需要空位。举个反例两个学校学校1有1支队伍学校2有1支队伍。双校交替后最后学校1的座位是19学校2的座位是20。此时只剩学校2但上一名队员恰好就是学校2这里碰巧需要隔位。如果把条件改成“单校阶段无脑跳两位”学校2最后一个位置从22开始也看不出问题。但换一个场景三个学校都剩余低编号学校先耗尽最后一轮for循环里某个学校A拿到了最后一个座位紧接着另一个学校B拿到当前轮最后一个座位。下一轮只剩A不会因为B还有剩余。只有当唯一的剩余学校恰好也是上一名队员时才要隔位。所以正确写法必须带着last判断不能一刀切。5.3 坑三输出格式和行尾空格座位号分配完成后输出阶段还有一个隐蔽的坑每行10个座位号行内空格分隔行尾不能有多余空格。很多处理不当的代码是“先输出数字后输出空格”导致每行末尾多一个空格被判格式错误。稳妥做法是先判断位次if (j % 10 ! 0) cout ; cout seat[i][j]; if (j % 10 9) cout \n;另外每个学校输出前要记得打印“#编号”这个前缀放在分配结果之前不是每一行都打印。忘了输出“#”等于整道题白做。6. 调试技巧与扩展思路6.1 把分配过程打出来看模拟题的调试最有效的方式不是设断点也不是看最终答案而是把“每轮给谁发了哪个座位号”按步骤打印出来。比如在代码里临时加一段cout round: pos pos school i rem rem[i] endl;然后拿边界数据跑一遍看着座位号一路涨上去你会立刻发现是在哪个节点多跳了一位、少跳了一位。这种逐行打印的方式对理解这类“状态驱动型”模拟题特别有帮助。我就是靠打印过程定位到“无脑跳两位”那个bug的——打印结果里单学校的第一个座位变成了2一眼就看出来问题。6.2 还能怎么优化推公式替代模拟的讨论模拟解法已经足够通过题目但对学有余力的人来说这道题还可以继续思考一个优化方向能不能不维护逐人的座位表直接算出每个学校每一支队第一个人的座位号思路大概是先找所有学校中人数最多的那个其余学校的人数总和决定了多校交替阶段的轮数当人数最多的学校进入单校阶段后可以通过当前剩余人数推算出它接下来每一个座位的号码。这是一种数学化的解法代码会更短但边界条件更绕稍不注意就会推出一个错两行的公式。我的建议是竞赛中以稳为主模拟解法已经能满分通过不需要过度优化。不过这个“先模拟、再推公式”的过程本身就是很好的算法训练。你可以在本地写完模拟后尝试对同一组数据用公式算一遍两边结果互相验证对理解题目规则会更深一层。如果哪天做题时碰到现在这种时间限制特别紧、数据量特别大的同类模拟题这种数学化思维就能派上用场。最后说一点个人体会天梯赛这类题最怕的不是算法难而是“觉得题目简单就上手写”。座位分配的规则里有明显的例外状态也就是单校隔位写代码之前一定要在纸上把多校交替、双校尾声、单校隔位三个阶段的样例各推一遍再开始动键盘。把状态拆清楚代码只是流水账状态没拆清代码就是一团乱麻。