火车购票是我在备考CCF-CSP认证时遇到的一道非常经典的模拟题。当时某同学拿它来问我开口就是一句这不就是找空座位吗有什么难的结果他前两次提交都拿了70分找来找去也查不出语法错误——后来我把他的代码跟题目规则一对照瞬间就明白了他把这排还有p个空位当成了这排有p个连续空位两个概念一混规则一就废了。这道题表面上是模拟实际上考的是你读题之后能不能把同排连续优先和最小空位兜底这两条规则用清晰的数据结构表达出来。题目本身不难一节车厢有20排每排5个座位总共100个。输入n条购票指令每条指令要买p张票1 ≤ p ≤ 5按规则分配座位并输出每次的座位号。数据量极小考的不是算法性能而是逻辑严密性。这篇文章我会把满分思路、带逐行注释的C/C代码、自测用例和考场避坑经验全部拆开讲适合正在刷CCF-CSP真题、或者被模拟题绕晕的同学直接抄作业。1. 题目还原别被火车购票四个字带偏了很多同学第一眼看到火车购票脑子里就开始想复杂的抢票系统、余票并发控制其实这道题跟真实购票系统没有半点关系。它只是一个纯粹的座位分配模拟题重点全在文字描述的规则里。1.1 车厢模型与座位编号规则车厢有20排座位每排5个总共100个座位。编号规则很固定第1排是1到5号第2排是6到10号第3排是11到15号依此类推第20排是96到100号。用代码建模的话最常见的做法就是int seat[20][5]seat[i][j]表示第i排第j个座位i从0开始j从0开始值用0表示空、1表示已占用。座位号换算公式是座位号 i * 5 j 1这个公式看着简单但很多人会在考场上一紧张写错。比如把i * 5 j 1写成i * 5 j那第一次卖票输出的就是0号座位整个编号整体左移一位。这种错很难通过眼睛查出来只能靠样例输出对比才能发现。1.2 两条分配规则一条比一条拗口规则一如果本次要买的p张票能在同一排找到p个编号相邻的空座位就必须安排在同一排并且选择编号最小的一段连续座位。这里有两个关键词需要同时满足同一排、编号相邻。规则二如果所有排都不存在能放下p张票的连续空位就退而求其次从1号到100号依次挑选p个空座位不要求同一排也不要求相邻。用生活化的场景来理解这就像在电影院选座规则一是你和朋友想连坐系统优先找一整排没人坐的连座规则二是全场确实没有连座了系统就按座位号从前往后给你挑散座哪怕你们几个人不挨着也没办法。那到底什么情况下会触发规则二就是每一排的连续空位数量都小于p的时候。注意我说的是连续空位不是空位总数。这是整道题最容易踩的坑。1.3 容易被忽略的边界条件题目里p最大是5所以当p等于5时只有一整排5个座位全空才能满足规则一中的连续5个座位。如果某排只有3个空位无论这3个空位怎么分布都不能买5张票时选这排。另外题目会保证购票总数不超过100个座位所以不需要编写余票不足的处理分支。这意味着我们只管分配不用考虑某个请求买不到票的异常情况。还有一点输出格式是每个购票指令输出一行座位号座位号之间用空格分隔。行尾不要有多余空格这是最基本的规范。2. 满分思路拆解模拟题的成败全在优先级数据量这么小20排5列一共100个座位n最大也就100极端情况下每条指令都买1张票随便怎么扫描都不会超时。那这道题还有什么技术含量有而且不少数据结构怎么选、两个优先级分支怎么写、连续区间怎么找每一个环节都有讲究。2.1 数据结构选型二维数组是首选有人可能会想用一维数组int seat[100]不是更省事吗座位号从1到100直接按下标访问连编号公式都省了。确实能用但判断同一排连续座位时会非常别扭。一维数组下你要判断从某个位置pos开始连续p个座位是否都空光是是否跨排就要额外处理如果pos是5或10这样的边界从它往后数p个就可能延伸到下一排。你必须时刻检查pos % 5 p 5这类条件稍不留神就会把第1排的末位和第2排的首位拼成连续座位。二维数组int seat[20][5]就不存在这个问题。行下标天然代表排列下标代表这一排内的第几个座位连续座位的检查就退化成一个单纯的横向扫描。数据结构把同一排这个约束直接编码进去了后面的逻辑写起来又直白又不容易错。我个人的考场习惯是能用直观的数据结构就绝不搞所谓的优化。二维数组占的内存几乎可以忽略不计但带来的编码效率提升是实打实的。特别是在时间紧张的考场里你不需要在脑子里额外维护一维下标到二维坐标的换算省下的全是出错的概率。2.2 第一优先级按排扫描找连续起点对每条购票指令p第一步是在整个车厢里找能提供p个连续空位的排。具体做法是双重循环外层循环从第0排遍历到第19排内层循环枚举这一排内连续座位的起点j。j的范围是0到5-p因为从j开始往右数p个座位必须保证不超出这一排的边界。然后检查从第j列开始连续p个座位是否全部为空。如果全空这串座位就是当前满足条件的最小编号连续区间。为什么敢这么说因为我们扫描的顺序就是第0排→第19排、同一排内第0列→第4列这正好等价于座位号1→100的顺序。第一次命中的区间就是全局编号最小的可分配连续区间直接分配这一组座位即可。这里有一个关键技巧检查连续区间时一旦发现某个座位被占用立刻终止当前起点的检查跳到下一个起点。不要傻乎乎地把整排扫完再判断虽然数据量小无所谓但提前break的代码逻辑更干净也更符合找到就停的直觉。2.3 第二优先级从1号开始找最小空位如果第一优先级整个扫描完都没有找到能容纳p张票的连续区间也就是assigned标志仍然是false这时候才进入第二优先级从1号座位开始按座位号从小到大扫描整个车厢遇到空座位就分配出去直到凑够p个座位。第二优先级的扫描顺序依然是从第0排第0列开始到第19排第4列结束所以分配出来的座位号必然是全车厢最小的p个空座。有人会问第二优先级会不会把某个排的座位拆得七零八落会而且这是规则允许的。比如第一排只空1号和3号第二排空6号这时候买2张票就会输出1和3而不是6。规则二的核心就是最小编号不是尽量连坐。实现第二优先级时还要注意必须从头扫描不能接着第一优先级失败的位置继续扫描。否则找出来的就不是全车厢最小空位而可能是中间某一段的空位。这是另一个高频失分点后面会专门讲。2.4 复杂度分析与考场意义每个购票请求最多扫描20排、每排5列、每列检查最多5个连续座位撑死也就500次操作。即使有100个请求总操作量也就5万次对任何评测系统来说都是瞬间完成的事。所以这道题真正的考察点不是算法复杂度而是你能不能严谨地处理业务规则。在CCF-CSP认证里这类规则模拟题出现频率很高核心套路都是一样的状态存储要准确、优先级判断要严格、边界条件要覆盖全。把火车购票吃透往后遇到类似题目思路会顺很多。3. C/C满分代码含逐行注释下面这份代码是我在考场上最常用的一套写法C和C语法通吃。全程没有花哨技巧就是老老实实模拟核心注释全部标好了。3.1 完整可运行代码#include bits/stdc.h using namespace std; // 车厢一共20排每排5个座位 const int ROWS 20; const int COLS 5; // seat[i][j] 0 表示第i排第j列座位为空 // seat[i][j] 1 表示第i排第j列座位已被占用 int seat[ROWS][COLS]; int main() { // 关闭输入输出同步加快cin/cout速度这题数据量小其实无所谓 ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // n条购票指令 while (n--) { int p; cin p; // 本次要购买的票数 bool assigned false; // 标记本次请求是否已经完成座位分配 // 第一优先级同一排找到连续p个空座位 for (int i 0; i ROWS !assigned; i) { // 枚举连续座位的起点列号 j保证 j p 不超出这一排 for (int j 0; j p COLS; j) { // 检查从 (i, j) 开始往右连续 p 个座位是否全空 bool ok true; for (int k 0; k p; k) { if (seat[i][j k] ! 0) { // 遇到已占座位 ok false; break; } } if (ok) { // 找到连续空位区间分配并标记占用 for (int k 0; k p; k) { seat[i][j k] 1; // 输出座位号注意控制空格格式 if (k 0) cout ; cout i * COLS j k 1; } cout \n; assigned true; // 本次分配完成 break; } } } // 第二优先级全局最小空位兜底 // 走到这里说明没有任何一排能提供p个连续座位 if (!assigned) { int cnt 0; // 已经分配的座位数 for (int i 0; i ROWS cnt p; i) { for (int j 0; j COLS cnt p; j) { if (seat[i][j] 0) { seat[i][j] 1; // 占用该空位 if (cnt 0) cout ; cout i * COLS j 1; cnt; } } } cout \n; } } return 0; }3.2 关键代码段拆解assigned标志是整个程序的交通枢纽。第一优先级一旦成功分配就把它置为true后续循环条件中的!assigned会帮助我们跳出所有外层循环避免同一个请求被分配两次。这个标志在第二优先级的判断中同样起着决定性作用。连续座位的起点枚举条件j p COLS值得单独说一下。当p等于5时j只能取0这意味着只有整排全空才能满足条件当p等于1时j可以从0取到4任何一个空座位都是连续1个空位判断自然恒成立。这个条件精确地表达了从起点开始数p个座位不能越界的约束。座位编号i * COLS j k 1是核心换算公式。i是排号j是连续区间的起点列号k是在这p个连续座位内的偏移量。每分配一个座位就立刻用这个公式算出真实座位号并输出。代码里加1是因为真实座位从1开始编号而行列下标从0开始。第二优先级中的cnt是计数器作用是保证凑满p个座位就停。每分配一个空座cnt加1同时cnt p作为双重循环的终止条件之一。这样写的好处是即使座位很多只要本次已经分够p张票就立刻退出全部扫描。3.3 考场速写版思路如果觉得上面这版写得有点重可以记住一个更精简的核心骨架对于每个请求先两重循环找连续座位找到就更新输出没找到就从左上到右下扫空位边扫边分配。很多同学喜欢把第一优先级封装成一个函数返回能否分配。我的建议是考场时间紧张直接在main里写两个循环反而更不容易出现函数参数传递的错误。4. 自测用例与手算推演代码写完不能直接交至少要跑几个用例确认逻辑没问题。下面我给两组自测用例一组是普通连续分配一组专门用来验证第二优先级。4.1 普通用例推演输入4 4 1 3 2这个用例刚好覆盖了第一排连续分配、第一排剩余单座、换排分配的情况。推导过程如下第一次请求买4张第1排1到4号全空输出1 2 3 4。 第二次请求买1张第1排还剩5号一个空位输出5。 第三次请求买3张第1排已满检查第2排6到8号三个连续空位输出6 7 8。 第四次请求买2张第1排已满第2排还剩9和10两个连续空位输出9 10。跑完这个用例程序输出应该是4行每行正好对应上面的结果。如果输出对不上优先检查座位编号换算公式i * COLS j 1是不是写错了。4.2 专门触发第二优先级的用例第二优先级是很多人没认真测过的分支。构造一个能强制触发它的用例连续输入40条买2张票的指令再加1条买3张票的指令。前40条指令会把20排座位都占掉4个座位即每排只剩最后一个座位空着。具体的分配过程是每排的前两个请求各占2个连续座位例如第1排先占1、2再占3、4剩下5第2排先占6、7再占8、9剩下10以此类推。40条指令过后20排的剩余空座分别是5、10、15、……、100。第41条指令买3张此时每一排只剩下1个空座位根本凑不出3个连续空位。第一优先级必然失败进入第二优先级后从1号开始找空座找到的是5、10、15三个座位输出5 10 15。这个用例的价值在于如果你写的程序在第二优先级阶段输出的是别的组合比如出现了6、7、8这种座位号说明你的第二优先级没有从全局最小座位开始扫描而是错误地接着第一优先级失败的位置继续找了。4.3 边界用例自查清单除了上面两组我建议交卷前再花一分钟跑这几个极端情形全部买1张票共100条请求。此时输出应该恰好是1到100每个数字单独一行。买5张票的请求。第一次输出1 2 3 4 5第二次输出6 7 8 9 10验证整排分配逻辑。第一排占满后第二排还剩几个零散座位再买超过剩余连续座位数的票验证换排和兜底分支。这些用例不用全部手算输出只要能跑通、肉眼观察分配符合规则即可。5. 常见错误与考场排查技巧火车购票这道题我在社区里见到过很多种失分姿势。这里我整理了一个高频错误速查表基本都是过来人踩过的坑。5.1 高频失分点速查表错误现象根本原因解决办法分配出来的座位明明不相邻却满足第一优先级用该排剩余空位数 p判断是否连续必须逐列检查连续p个座位的状态而不是只数空位个数一维数组下标越界或跨排被算作连续没有处理连续座位不能跨排的边界改用二维数组或在起点枚举时加上j p 5的判断第二优先级输出的不是最小空位失败后没有从座位1重新扫描而是接着上次的位置找第二优先级必须用独立的双重循环从第0排第0列重新开始输出结果整体缺1或多1座位编号公式写成了i*5j而非i*5j1用样例输入的第一次输出验证编号1到5号对应第一排行尾多了一个空格输出循环里无条件在两数之间打了空格用if (k 0) cout ;控制只在第二个及之后的数字前加空格某个请求莫名少输出或重复输出assigned标志没有在成功分配后及时置true每次成功分配后立即assigned true并在外层循环条件中加入!assigned其中最阴险的错误是第一种。它表面看起来输出也有座位号甚至某些用例能碰巧通过但只要构造一个剩余空位数够、但空位不连续的用例就会立刻暴露。判断连续的方法必须是对具体座位位置做扫描不能只看剩余数量。5.2 考场上如何快速定位规则理解偏差如果在考场上提交后分数不对但编译运行都没有报错问题基本就出在规则理解上。我个人的排查顺序是先看第一优先级。拿样例输入推演一遍手写出每一排座位的占用过程再对照程序输出的中间步骤找出第一个不一致的地方。一般在这个环节就能定位是连续判断写错还是编号最小没满足。再看第二优先级。构造一个强行触发第二优先级的用例比如上面的40个2票1个3票跑一遍。这一步主要验证兜底分支有没有从头扫描、是否输出了全局最小的那几个空座位。最后检查输出格式。CCF评测对行尾空格通常不敏感但害人之心不可有规范一点总没坏处。每题交卷前刻意检查一下循环输出空格的条件能省掉不必要的警惕。5.3 把这道题抽象成通用模板火车购票这类规则模拟题本质上都可以归纳成四步第一步设计状态的数据结构把题目中的车厢座位排映射成数组第二步拆解分配规则明确优先级顺序第三步按优先级写出干净的分支逻辑第四步在更新状态的同时完成输出。我在准备CCF-CSP的过程里发现很多模拟题都是这个套路只是包装不同。有的题把座位换成了停车场车位有的把购票请求换成了停车场门禁记录但核心逻辑大同小异状态更新要准确优先级判断要严谨边界条件要考虑周全。这道火车购票我前前后后刷了三遍。第一遍看思路第二遍练手速第三遍用来给同学讲题每次都有新的收获。如果你也在备考CCF-CSP强烈建议把这道题作为入门模拟题反复吃透——它几乎囊括了规则模拟题的绝大多数坑点把它的解法刻进脑子里后面遇到更复杂的模拟场景你会感谢今天这份认真。