每个月的周末我都会在洛谷上挑一场比赛做做保持手感。这回看到“语言月赛 202601”里的 B4477 “考场安排”我第一反应是又来一道中文阅读理解题。语言月赛的定位本来就是给刚开始学编程的同学练手题目不会上太深的算法但“看得懂中文和写得对代码”之间往往隔着一条鸿沟。这篇不是官方题解也不想复述一遍标准做法我更想记录自己拿到题之后是怎么把一串文字描述拆成可以编程的模型、又在哪些地方翻车的顺便聊聊这类排座位问题的通用套路。我自己常年给学弟学妹讲题发现一个规律越是 B 开头的入门题越容易让人卡在“想的和写的完全不是一回事”。考场安排这四个字听起来接地气但落到代码里就是一堆变量、循环和边界条件。下面直接进入正题。1. 先别急着写代码语言月赛的题到底在考什么1.1 从“考场安排”这个黑盒开始很多刚接触竞赛的同学拿到题目会习惯性打开编辑器看完前两行就开始写循环。这是最容易犯错的一步。语言月赛的题目喜欢把信息藏在很“口语化”的描述里比如“某些同学不能坐在同一个考场”“每个考场最多坐多少人”“要求尽量少开考场”等等每一句话都是一个约束条件。你少考虑一句样例可能都能过但一到测试点就全盘 WA。我看到“考场安排”时做的第一件事不是写代码而是把题面当成一份需求文档来读。我会拿一张草稿纸把题目里出现的所有实体列出来实体典型信息在代码里的样子考生编号、所属班级、可能的限制关系数组下标或结构体对象考场容量上限、编号数组存的剩余座位限制条件是否允许同场、是否有优先顺序布尔数组或排序规则目标最少考场数、最大可行容量或可行方案答案输出把这个表列出来之后题目就不再是一段话而是一组明确的数据关系。B4477 这类“考场安排”题不管具体约束怎么变最后基本都会落进两类模型里一类是容量分配问题相当于把若干个体往一个固定容量的容器里塞另一类是冲突检测问题相当于给一张图做染色或判断约束是否矛盾。你可以先猜是哪一类但一定要用题面里的原话来验证不能想当然。1.2 从输入输出倒推题目模型输入输出格式其实是题目最好的“自述”。有些人的读题习惯是从头读到尾我的习惯是先看输入和输出再回头看描述因为输入变量已经暗示了模型如果输入里有“考场容量”“人数”这样的数字多半是贪心或模拟如果输入里出现了“两个人之间不能同场”这种成对信息多半要开一个二维关系数组或者建图。你不要小看这一步很多人在草稿纸上分析得头头是道一写代码却发现没开够数组或者把一对关系的读入顺序搞反了。我当时给自己定的读题流程是圈出输入里的每个变量给它们起一个能对上题面的名字比如n是考生数m是考场数cap[k]是第k个考场的容量。圈出输出要求明确要输出的是一个数还是一整个方案。手推一遍样例用最朴素的方式在纸上模拟分配过程不追求算法只追求“逻辑能跑通”。想清楚样例输出的每一步是由哪条规则触发的。语言月赛的题通常样例非常温和手推样例不会花太多时间但能帮你建立“题目说的到底是什么”的直觉。我当时推完第一组样例发现答案是按某种顺序依次塞进去的于是心里就有了个猜想这道题八成要用排序加贪心。后面再去验证这个猜想而不是直接裸写一个sort就交。2. 考场安排的贪心解法什么时候排满是对的选择2.1 排序加贪心最稳的基础姿势如果说 B4477 有什么值得认真对待的考点我认为“贪心策略的选择”是核心。对于容量型考场安排一个很自然的做法是把考生按某种关键信息排序然后依次安排进当前剩余容量最合适的考场。常见的两种贪心策略是“先到先得”和“最佳适应”。我在这里放一段通用性的 C 伪代码不是 B4477 的原题代码但结构很典型。你可以把它当成积木根据题面约束调整排序关键字和判断条件。#include bits/stdc.h using namespace std; struct Student { int id; int val; // 这里代指排序关键字比如人数、优先级、批次 }; bool cmp(const Student a, const Student b) { if (a.val ! b.val) return a.val b.val; // 大的在前 return a.id b.id; // id小的在前保证稳定性 } int main() { int n, m; cin n m; vectorStudent stu(n); for (int i 0; i n; i) { cin stu[i].id stu[i].val; } vectorint roomRemain(m); for (int i 0; i m; i) cin roomRemain[i]; sort(stu.begin(), stu.end(), cmp); // 贪心分配把当前学生安排进第一个还能塞下的考场 vectorint ans(n, -1); for (int i 0; i n; i) { bool ok false; for (int j 0; j m; j) { if (roomRemain[j] stu[i].val) { roomRemain[j] - stu[i].val; ans[stu[i].id] j; ok true; break; } } if (!ok) { cout 无法安排 endl; return 0; } } cout 安排成功 endl; return 0; }这段代码的时间复杂度是 O(n*m)考场数不多时完全够用。如果 m 很大、数据量再往上涨可以把每个考场的剩余容量塞进一个优先队列每次取容量最大的考场尝试把复杂度降到 O(n log m)。语言月赛的数据范围通常不会逼你到这一步但理解“优先队列换贪心效率”是个很好的进阶点。2.2 贪心会翻车的地方和验证方法贪心算法最大的问题不是“想不到”而是“想当然”。比如“优先排大的”有时确实是对的但换了排序关键字就可能全错。我见过很多人在类似题目里直接按人数从大到小排结果把一个容量很大的考场留到最后却没人放反而多开了考场。要验证贪心是否成立可以用一个很朴素的思想实验假设你有一个最优方案如果里面有两个元素和你贪心安排的结果不一致能不能把它们的顺序交换一下使得方案不会变得更差如果每次都能做到那贪心就是安全的。为了保险我通常会在草稿纸上构造一个很小的反例。比如假设有三个考场容量分别是 5、4、4有四个待安排的批次所需容量是 3、3、2、2。如果按“从大到小”排序先放 3 和 3再放 2 和 2结果是占满 5 和 4剩下一个空考场开两个考场就能解决但如果某个贪心策略先放 2 再放 3很可能就要开三个考场。这个例子说明同一个分配目标策略不同结果完全不同。所以做这道题时我会反复读题面里的“要求”两个字到底是要“充分利用每个考场的容量”还是要“保证人数多的班级优先选考场”还是要“任意两个人之间不冲突”。这三者对应的代码可能完全不同。语言月赛的题很少故意出怪题通常题面怎么描述策略就怎么定你顺着描述走的正确率远高于自己发明套路。3. 从“思路对”到“代码对”我踩过的三个细节坑3.1 边界条件和数组大小考场编号与考生编号千万别混第一遍提交我很快写出了主逻辑样例也过了但交上去 WA 了两个点。我到后来才发现是数组问题题目里考生编号可能从 0 开始也可能从 1 开始考场编号同样如此。我在写输出的时候用错了下标导致所有编号整体偏移一位。这种错在语言月赛特别常见因为出题人喜欢用“第 1 个考场”“第 2 名考生”这种自然语言而你在代码里一不留神就用数组从 0 开始的习惯去访问。我的建议是在读完输入后立刻做一个“编号归一化”凡是题目里说第几就统一转成从 0 开始的下标最后输出时再转回去。所有后续逻辑都基于同一个约定能少踩很多坑。另一个边界问题是“容量恰好为 0 的考场到底算不算可选”。有的题面会说“空出来的考场不需要安排”有的则说“只要考场存在就可以塞人”。如果你不专门处理容量为 0 的情况循环里就可能写出无限循环或者除零错误。我当时是用一个计数器统计还有座位余量的考场数每次减掉一个学生就重新检查一遍虽然啰嗦但绝对安全。3.2 数据范围与类型int 还是 long long答案是唯一解还是方案我遇到过不少选手思路全对却因为忘开long long丢掉 20 分。语言月赛的部分题目会故意在数据范围里埋雷比如考场容量之和超过了int上限或者输出的是一个需要累乘的结果。我的习惯是只要题目描述中出现“不超过 10 的 9 次方”或“总数可能非常大”这样的字眼直接全部用long long反正内存不缺这一点。还要注意输出格式。B4477 如果要求输出“最少需要开启的考场数量”那答案往往是一个数如果要求输出“具体的座位分配方案”那就要注意行末空格和换行。洛谷的 Special Judge 有时候允许答案不唯一但格式错了照样判错。我的做法是先把要输出的内容构造成一个字符串最后统一打印避免中间漏了换行。3.3 一交就 WA 的隐藏原因多组数据、排序稳定性与读入顺序有一类错是最冤的题目明明说“数据可能包含多组测试”你却只做了一组或者排序函数写得不严格导致相同关键字的元素顺序不确定而题目恰好又要求按编号升序输出。C 的std::sort是“不稳定排序”你在cmp里不写第二关键字相同值的元素顺序就无法保证。所以任何涉及输出的排序我都建议加上编号作为次关键字。读入顺序也值得单独说。有些考场安排题会先读考场信息再读考生信息有些则相反。你写cin n m的时候看起来无所谓但后面所有for循环的边界都依赖这个顺序。我自己的技巧是每次读入循环里把手里的变量和题面变量名逐字核对一遍强迫自己不看代码看注释。为了把边界情况测明白我给自己定了一张自测用例表。每当写完一道模拟或贪心题就按这个表造数据测试场景具体数据想暴露的问题最小规模1 个考生、1 个考场循环边界、数组越界所有考生挤爆一个考场容量和刚好等于总需求等号判断每个人单独一个考场考场数和人数相同且容量都为 1极端分配容量有一个特别大某个考场容量远超其他之和贪心排序策略多组数据混合每组之间考生、考场数不同清空状态、重置统计这张表帮我在本地打掉了至少三次 WA。你也可以直接把类似表格写进自己的刷题笔记里。4. 如果模型更复杂从“排考场”到“资源分配”4.1 冲突关系用并查集还是图染色容量分配只是考场安排的一个面另一面是“冲突限制”。如果题面里出现“第 a 个考生和第 b 个考生不能在同一考场”这类条件那你面对的就是一个图论问题。这里有两种常见做法并查集判断“是否矛盾”如果冲突关系具有传递性例如 a 和 b 不能同场、b 和 c 不能同场导致 a 和 c 也必须分开那可以用带权并查集维护“同类”与“异类”关系。但由于“不同考场”并不等价于“同类”有时候并查集不是最合适的模型。二分图染色判断“能不能用两个考场解决”如果把每个考生看作点、冲突看作边一个考场能否满足所有约束等价于判断这张图是不是二分图。用 BFS 给每个点染色一旦发现某个点和它相邻点同色就说明约束无解。语言月赛大概率不会单独考到这么深但 B4477 把背景设为考场安排其实是一个很好的引子。它会让你意识到现实里的“冲突检测”在代码里就是一连串相邻点染色问题并不神秘。4.2 二分答案加检查最少考场数的通用解法如果题目不问“能不能安排”而是问“最少需要几个考场”很多新手一上来就想用贪心求最少值但这不总是可行。遇到这类目标我更推荐“二分答案”这个通用框架猜一个考场数 k然后写一个check(k)函数判断 k 个考场是否足够安排如果可以就减小 k否则增大 k。bool check(int k, const vectorint need, int capacity) { int roomCnt 0, rem capacity; for (int x : need) { if (x rem) { roomCnt; rem capacity; if (x rem) return false; } rem - x; } return roomCnt 1 k; }这个check的本质是一个简单的“连续装箱”判断把需求按顺序塞进容量固定的考场如果塞不下就新开一个。注意这个代码的前提是“顺序已经给定”如果题目允许任意调整顺序那就要先排序再用这个函数。二分答案的好处是思路清晰、不容易被贪心反例坑代价是多一个 log。题目数据范围不算大时这往往是最稳的方案。4.3 从竞赛题到现实排考系统很多人觉得竞赛题是空中楼阁但“考场安排”这类题其实离现实很近。学校每次期中期末排考场要考虑的约束比题目里多得多同一个老师不能同时监考两个考场、同一班级的学生尽量打散、教室容量不同、某些学生因为选科不同不能安排在同一个时间段。如果你把竞赛里的“考场”替换成“服务器”、把“考生”替换成“任务”它就变成了负载均衡问题把“教室容量”换成“带宽上限”它就变成了装箱问题。B4477 这种题表面上是在排考场实际上是在训练你如何把约束写进代码。这个抽象能力比 AC 本身值钱得多。5. 给准备入坑语言月赛的朋友一点实话5.1 练什么语法速度与模拟题的肌肉记忆想打好语言月赛不需要上来就啃图论、网络流。你真正需要的是三样东西快速读完题面并提取变量的能力、熟练的数组与循环操作、以及可靠的排序与模拟实现。我建议把所有涉及“座位分配”“顺序处理”“任务排队”的简单题都刷一遍因为它们就是语言月赛最偏爱的题材。语言月赛考的是“你能不能把想的写出来”所以平时练习一定要在编辑器里写完整程序而不是在草稿纸上画画就觉得自己会了。我在给朋友讲题时经常说一句话能说清楚思路只说明你懂了一半能一次编译通过、在洛谷上拿到 AC才算真正掌握了语言基础。5.2 怎么练把每次 WA 都当成分析样本很多新手看到红色 Wrong Answer 就心态爆炸然后直接去看别人题解。这样练题效率其实很低。我更建议你保留自己第一次提交的代码在后面标注“我错在哪里”。这就像做错题本一样每次 WA 都是你思维习惯里的一个盲区。我就有过一个记录表里面写满了“数组开小”“没加第二排序关键字”“输出多了个空格”这类问题两个月后回去看几乎不再犯同样的错了。5.3 心态入门赛是用来建立信心的语言月赛的题不会故意用阴间数据卡人它的选拔对象是刚学会循环和数组、想试试自己能写多长代码的人。所以哪怕你只 AC 了两三道也是一种有效反馈说明你已经能把一个生活场景翻译成程序逻辑了。不要拿自己和别人比 AC 数你要比的是上一次的自己这周能不能多过一道模拟题、少一次无效提交。我在做 B4477 的过程中最大的收获不是某个排序技巧而是养成了一套稳定的“从文字到代码”的处理流程先列实体再画约束最后写小样例验证。这套流程几乎能迁移到所有中文描述的入门题上。如果你现在正准备报名下一场语言月赛不妨也试着给自己定一条硬规矩看完题面十分钟内不许动手写代码。排考场只是开端以后你还会遇到很多被层层包装过的题目背后都是你熟悉的数组、排序和判断。把这些基础功打扎实B4477 会是你很长一段时间里的手感刻度尺遇到类似的题时你会想起今天踩过的坑然后自然而然地绕开它们。