★ FEATURED ARTICLE 天梯赛座位分配这题每年打CCCC的队伍里总会有人在上面栽跟头。题目本身不涉及高深算法不排序、不搜索、不动态规划就是纯模拟可越简单的题越容易在细节上翻车。N所学校、每校M支队、每队10个人座位从1号开始按学校编号轮流分配同一所学校的人不能坐在相邻位置最后只剩一个学校时还要隔一个座位坐。规则三句话能说完但真到赛场上能把这三种情况处理干净、输出格式一点不错的队伍其实没那么多。这篇文章就把这道题从题面到代码完整拆一遍给正在备赛的选手做参考也适合所有想练好模拟题基本功的算法新手。1. 题目到底在考什么题面解读与核心考点1.1 一句话讲清题目读入一个正整数N代表参赛学校数量接下来N个整数分别是每个学校的队伍数。每个队伍固定10个人所以第i个学校的参赛人数是队伍数乘以10。现在要给所有选手排座位座位号从1开始连续递增分配顺序按照学校编号1、2、3……N循环轮转每次给一个学校分一个座位。要求是同一个学校的选手不能坐在相邻的两个座位上。当比赛进行到只剩一个学校还有人没座位时这个学校的人需要隔一个座位坐。最后按学校输出每个选手的座位号每10人一行学校之间空一行。这个题目适合用来练习模拟题的基本功因为它的规则全部来自实际生活场景没有人为设计的抽象模型理解起来没门槛。但正因为贴近现实边界情况特别多比如“恰好在某一轮分完”“最后一所学校剩单数人”“只剩一个学校但上一次不是它”这些情况都要在代码里表达清楚。1.2 真正的难点不在算法在边界这题最迷惑人的地方在于它看起来像一个循环队列问题很多同学第一反应是维护一个学校队列每次pop出队首学校分配座位再push到队尾。这个思路大方向没错但有两个边界处理不好就会WA。第一个边界是“同一学校不相邻”究竟什么时候会触发。很多人以为只有当学校数量为1时才需要隔位其实不是。如果当前轮到的学校恰好就是上一次分配座位的学校那么必须先把座位号加1跳过再分配。在所有学校都还有人时由于轮转顺序固定这个情况不会发生但一旦某些学校提前分完剩余学校集合发生变化轮转仍然按编号从1到N循环就可能出现连续两次轮到同一个学校的情况。第二个边界是“只剩一个学校”的判断不能只做一次。不能用初始学校数来判断因为随着分配进行学校会陆续分完。必须在每轮分配前动态判断当前剩余学校数量或者用一种更巧妙的写法把“当前学校是否等于上一次学校”作为是否需要跳座的统一条件。这两种写法下面都会讲到。1.3 手推两遍样例彻底理解分配过程先看最简单的情况2所学校每所学校1支队伍共20人。按照编号1、2循环第1个人坐1号第2个人坐2号第3个人坐1号……交替进行最后学校1拿到的是1、3、5、7、9、11、13、15、17、19学校2拿到的是2、4、6、8、10、12、14、16、18、20。两个学校交替分配每个学校内部座位相隔2符合同校不相邻的规则。再看只剩一个学校的情况只有1所学校1支队伍共10人。第1个人坐1号第2个人就不能坐2号了因为1号和2号相邻且同校所以跳过2号坐3号接着跳4号坐5号最终座位号是1、3、5、7、9、11、13、15、17、19。这就是题目里“隔一个座位坐”的直观含义座位号变成了公差为2的等差数列。这两个例子覆盖了题目的两种核心情况把代码逻辑与座位号的变化对应起来后面写代码时心里就有谱了。2. 核心思路与方案选型为什么直接模拟就能过2.1 不排序不贪心老老实实按规则走这道题最容易走偏的思路是试图推导座位号公式。比如有人会想第i个学校的第k个人会不会有一个通项公式确实在“所有学校人数完全相同”的前提下会有规律但一旦各校人数不同提前分完的学校从循环中退出公式就会变得非常复杂而且极易出错。正确做法就是模拟。把“下一个待分配的座位号”用一个变量cur保存把“上一轮分到座位的学校编号”用last保存。每次循环执行三件事找到当前应该分配座位的学校如果这个学校和last相同就先cur加1然后把cur座位号分配给该学校最后更新last并让cur加1。循环总次数就是所有学校的总人数。这种暴力模拟的时间复杂度是O(总人数×N)总人数最多10万N最多100乘起来也就一千万级别C毫秒级跑完Python也能在几秒内完成。比赛时完全不需要优化重要的是把逻辑写对。2.2 数据结构怎么选vector数组就够我习惯用一个一维数组people[i]表示第i所学校当前剩余未分配的人数初始值为队伍数乘10。每次给学校分配一个座位后people[i]减1。当people[i]变成0说明这所学校已经排完了。再开一个二维结构存每个学校的座位号。C里用vectorvector ans(n1)Python里用列表的列表。为什么不直接用二维数组因为每个学校人数可能不同用vector能动态按需扩容不用预先开死空间。当然这题数据量小开int ans[105][1005]也完全没问题但我个人更推荐vector语义清晰也顺手避免了数组越界的风险。选择这种数据结构的关键理由是我们只关心“还有什么学校没分完”和“每个学校已经分了哪些座位”不需要关心队伍之间的关系。题目最终按学校输出不需要按队伍拆分所以没必要额外记录队伍维度记录到人这一层就够了。2.3 统一用last判断跳座省掉剩余学校计数很多题解会先数一数当前还剩几所学校如果只剩1所就在分配前把cur额外加1。这个做法没问题但需要每次循环都遍历一遍学校来计数多少有点啰嗦。其实有一个更简洁的统一写法每次找学校时优先找“还有人且编号不等于last”的学校。如果找到了正常分配不需要跳座如果找不到说明所有剩下的人都在last这所学校这时候才让cur加1再分配。这个写法的巧妙之处在于它把“只剩一个学校”这个全局状态转化成了“当前轮到的学校等于last”这个局部状态不需要单独维护剩余学校数量。理解这一点代码会变得非常干净也更容易排错。我比赛时就用的这个写法一次通过。3. 完整实现与代码逐段拆解3.1 可直接提交的C代码下面这版C代码是我调试完的最终版本逻辑和上面分析的一致提交到OJ能直接通过。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint team(n 1), people(n 1); int total 0; for (int i 1; i n; i) { cin team[i]; people[i] team[i] * 10; total people[i]; } vectorvectorint ans(n 1); int cur 1; // 下一个待分配的座位号 int last 0; // 上一次分配到座位的学校编号0表示还没有 while (total 0) { int sid -1; // 先找未分完且不等于last的学校 for (int i 1; i n; i) { if (people[i] 0 i ! last) { sid i; break; } } // 找不到说明只剩last这所学校还有人了需要隔位 if (sid -1) { for (int i 1; i n; i) { if (people[i] 0) { sid i; break; } } cur; } ans[sid].push_back(cur); people[sid]--; last sid; cur; total--; } for (int i 1; i n; i) { cout # i \n; for (int j 0; j (int)ans[i].size(); j) { if (j 0 j % 10 0) cout \n; if (j % 10 ! 0) cout ; cout ans[i][j]; } cout \n; if (i n) cout \n; } return 0; }3.2 关键代码段逐行说明先看初始化部分。team[i]是第i个学校的队伍数people[i]是该校总人数total是所有学校人数之和。while循环以total为计数保证每个选手恰好分到一个座位这个设计比“按学校遍历再嵌套按人遍历”更符合模拟的实际顺序因为座位是按全局顺序分配的。再核心的找学校逻辑。第一个for循环从头扫到尾找编号最小、还有人且不等于last的学校。这里有个细节如果没找到不等于last的学校但剩余学校不止一个且都等于last——这种情况不存在因为两个不同学校不可能都等于同一个last所以“第一次循环找不到”和“只剩一所学校”是等价的。找到sid后如果sid等于-1进入第二个循环取编号最小的还有人学校也就是last自己然后cur加1实现隔位。这里cur的作用是空出当前座位让上一个学校和下一个学校之间多隔一个位置。分配座位时先push当前cur然后people[sid]减1last更新为sid最后cur加1准备下一个座位。三个更新语句的顺序一定不能乱尤其是last更新必须在people减1之后否则下一次判断会用到旧值。输出部分要特别注意换行逻辑。j%100表示新的一行开始但j0时不需要换行所以加了j0的条件。行内用j%10!0控制空格保证行尾没有多余空格。学校间空行用if(in) cout\n实现这样最后一所学校后面不会多出空行。这些输出细节任何一个不对都可能被判格式错误。3.3 Python参考写法用Python写这题时思路和C一样但有几个语法细节要注意。完整代码如下import sys n int(sys.stdin.readline()) team list(map(int, sys.stdin.readline().split())) people [0] * (n 1) for i in range(1, n 1): people[i] team[i - 1] * 10 total sum(people) ans [[] for _ in range(n 1)] cur 1 last 0 while total 0: sid -1 for i in range(1, n 1): if people[i] 0 and i ! last: sid i break if sid -1: for i in range(1, n 1): if people[i] 0: sid i break cur 1 ans[sid].append(cur) people[sid] - 1 last sid cur 1 total - 1 for i in range(1, n 1): print(f#{i}) for j, val in enumerate(ans[i]): if j 0 and j % 10 0: print() if j % 10 ! 0: print( , end) print(val, end) print() if i n: print()Python要特别注意print的end参数默认是换行想在同一行连续输出数字就得指定end。读完队伍数后输入可能分布在多行稳妥起见用split后一次性读入这样能兼容输入换行的各种情况。4. 常见问题与排查技巧实录4.1 三个踩过的坑每个都是WA第一个坑是循环变量用错了。我最初写的是for(int k0; kn; k)外循环然后内层给每所学校连续分配people[i]个座位这样一来前半段全是1号学校的人后半段全是2号学校的人完全没有交替直接WA。后来改成用total作为总人数循环每次只给一个学校分一个座位交替效果才正确。第二个坑是last更新时机。有一版代码我先把cur存进ans然后cur加1最后才更新last结果在下一轮判断时last还是旧值导致跳座逻辑完全错乱。这里强调一下last必须在每轮所有操作中最先更新严格来说是在确定sid之后立刻更新然后再处理cur和people。第三个坑是输出格式。题目要求每个学校之间有一个空行但很多人的第一反应是每所学校末尾加一个空行结果最后一所学校的末尾也多了一个空行被判格式错误。正确的做法是只有不是最后一所学校时才在末尾输出空行这一点代码里用if(in)控制。4.2 常见WA场景速查表错误表现可能原因解决方案答不对样例学校座位连续堆积内层循环一次给一个学校分完全部座位改成按总人数逐个座位分配只剩一个学校时座位不隔位没有判断当前学校与last相同用lastsid判断并cur多所学校的座位错乱某校连续出现轮转顺序没有回到编号小的学校每次从1到N完整扫一遍不缓存当前位置行尾多空格输出时没判断是否是行首用j%10!0控制空格最后一所学校后多空行无条件在每所学校末尾输出空行加上in的判断数组越界或段错误开了固定二维数组但某校人数超限用vector动态存储座位号这张表基本覆盖了这道题在OJ上最常见的几类错误。出现WA时不要盲目改先拿样例手推一遍再对着表检查逻辑比自己瞎试效率高得多。4.3 推荐两个调试技巧手推小数据和随机对拍调试这题最有效的方法是先造一个极小的数据手推结果。比如N2、每校1队手推出来学校1的座位是奇数1到19学校2是偶数2到20如果程序输出和这个不一致说明轮转逻辑有问题。再比如N3、每校人数分别是20、10、10这个数据能同时测到“两所学校同时分完”和“只剩一个学校后的隔位”两个边界手推一遍再对程序输出几乎能定位所有问题。对于有编程环境的情况我更推荐写一个简单的对拍脚本。生成一个暴力的参考实现再用随机数据跑两个程序对比输出。这道题的暴力实现很简单用一个队列存学校编号每次出队一个学校分配座位再判断是否入队。两个版本输出一致就说明逻辑基本没问题。对拍能覆盖到手动构造想不到的边界组合比如最后一所学校恰好还有1个人、三所学校同时只剩1个人等极端情况。5. 复杂度分析与竞赛实战心得5.1 时间和空间复杂度估算先看时间复杂度。外层循环精确执行total次也就是所有学校的参赛人数之和。第一次找学校的循环最坏情况下扫描N个学校第二次找学校在最坏情况下再扫描N个学校。所以单轮最坏是2N次操作总复杂度O(total×N)。按题目通常的数据范围N100、每校最多100支队伍来算total不超过10万总操作约一千万次C轻松跑进0.1秒Python在2秒限制内也稳。空间复杂度主要看ans数组它存储了所有座位号个数也是total所以空间复杂度O(total)。people数组只存学校剩余人数空间O(N)。这个复杂度放在天梯赛L1级别的题目里属于非常宽裕的不需要任何额外优化重点全在代码正确性。5.2 模拟题在比赛中的定位稳拿分才是硬道理天梯赛这种团体赛比的不是谁最快写出最优解而是谁能在有限时间内把该拿的分都拿到。L1-049属于L1组里偏后的题目分值不算低它的定位就是考察基本的代码功底和逻辑严谨性。这类题的特点是一旦想清楚代码很短几乎没有调试成本但想偏了可能卡很久。我的建议是拿到题先别急着写花两分钟把样例手推一遍确认自己理解的和题目一致。特别是这种有特殊规则的模拟题手推样例能把题目里含糊的表述具体化能避免“题都读错了还写半天”的尴尬。写完之后再用一两个自造的边界数据自测比如只有1个学校、有学校人数为0、所有学校同时分完这些情况下程序也能正确输出就可以放心提交了。5.3 这题还能怎么变举一反三的思路把题目条件稍微改一改就能变成新的练习题。比如每队人数从固定10改成输入给定的k代码里只需要把people[i]team[i]*10改成team[i]*k其他逻辑完全不变。再比如要求按队伍维度输出座位也就是每个队伍内部10个人的座位号单独成组这时只需要在输出时对ans[i]按10个一组切片也几乎不用改核心分配逻辑。还有一种变体是座位间隔规则变化比如改成“同一队伍的人不能相邻”那last记录的对象就从学校变成队伍编号判断条件从i!last变成当前队伍编号不等于last。核心的“找目标并判断跳座”框架还是一样。这说明模拟题的关键是找准“状态”和“转移规则”状态一变规则一变代码跟着小改即可。练会这一道题等于掌握了一类模拟题的通用解法。最后分享一个我自己的习惯这类题目提交前一定会检查输出部分是否有多余空格和空行。格式错误是模拟题最冤的失分方式逻辑全对却因为一个换行扣分谁遇到谁知道。多花十秒钟对着输出格式要求逐条核对比事后返工强得多。
阅读完成 · 觉得有帮助？
