我翻到这道“彩虹瓶”的时候第一反应是这不就是个模拟题嘛按流程走一遍完事。但真正上手写代码之后我才发现这题把栈的两个核心特性——先进后出和容量受限——考得非常细。尤其是“装好一个球之后必须回头检查货架顶上的球能不能继续装”这一步逻辑漏掉一半判题结果就是一片红。这题的场景其实很生活化工厂按编号顺序生产彩色球彩虹瓶也要按编号顺序装填但送货顺序会被打乱工人又不能把球扔到一边不管只能放到一个容量有限的货架上暂存。说白了就是一个“队列生产、栈式缓存、顺序消费”的模拟题数据结构基础扎实的人三分钟能写完但没理解透栈的“只能在顶部操作”这个限制的人会反复栽在同一个坑里。1. 题目建模把“装瓶子”变成“栈操作”很多朋友看到这类描述长的题容易慌觉得逻辑很多。其实拆到底只有三个关键信息生产顺序、装配要求、货架规则。1.1 生产顺序与装配顺序先说最核心的一条工厂按 1 到 N 的编号顺序生产彩色球也就是说球是依次从传送带送来的顺序固定为 1、2、3……N。但题目给的是打乱后的到货序列所以实际场景是“球按照数列顺序被送过来但工人不能挑送过来哪个就看哪个”。彩虹瓶这边也有严格要求第一层必须放颜色编号为 1 的球第二层放 2第三层放 3一直到第 N 层放 N。换句话说不管球怎么个到货顺序最终装瓶顺序必须是严格的 1、2、3……N没有变通余地。这两条叠加起来就形成了一组矛盾生产和装配都要求“按顺序”但中间的传递序列被打乱了。如果没有一个中转暂存区那只要送来的球不是当前需要的编号这活就干不下去了。1.2 临时货架就是一只栈工人旁边有一个临时货架规则是每次只能从最上面取球放球也只能放到最上面货架最多放 M 个球。这就是教科书里标准的栈结构先进后出只能在栈顶操作。为什么要设计成栈而不是一个可以任意取放的托盘我猜出题人就是想让做题人不绕过“先进后出”这一核心限制。假设货架容量是 3生产序列是 3、2、1、4那工人先拿到 3不是当前需要的 1放到货架上拿到 2也不是 1放上去拿到 1正好需要装瓶装完 1发现货架顶上是 2取下来装装完 2货架顶上是 3取下来装最后拿到 4正好装完。整个操作中货架上的球被取走的顺序恰好和放入顺序相反这就是栈。1.3 判定结果不是所有序列都能成功题目要求对每个测试序列输出 YES 或 NO。YES 表示按这套规则能把所有球按编号装进彩虹瓶NO 表示过程中会出现“当前需要的球没来货架又满了装不了”这种无法挽回的局面。这里有个容易被忽视的细节即使某个序列最终失败了但题目给出的输入数据不会因此中断剩下的球还是会继续送过来。所以程序在处理失败的序列时不能直接跳出不管而是要把这一行剩余的数字全部读完并丢弃然后才能处理下一条数据。这个点很多第一次写这类题的朋友会踩后面我会单独拿出来讲。2. 核心思路模拟装配线每一步都只做两件事把模型梳理清楚后剩下的问题就是怎么用代码模拟工人操作。核心思路不复杂但有几个判断位置必须想明白。2.1 模拟流程的骨架我维护两个状态need当前彩虹瓶需要的颜色编号初始为 1表示从 1 号球开始装。s一个栈表示工人手边的货架栈中自底向上依次是最早到货、最近到货的球。对到货序列中的每个球x就两种可能 第一种x need不需要上货架直接装瓶然后need。装完之后不能立刻处理下一个球得先看一眼货架顶上是否正好是更新后的need如果是就继续取这个“连锁反应”要一直持续到货架顶的球对不上号为止。 第二种x ! need那就只能放上货架。如果货架已经放了 M 个球再放就溢出了当前序列直接判 NO如果没满就把x压入栈顶。数据全部处理完之后还要检查两个条件过程中没有出现过程序中断的错误标记以及最终need N 1也就是说所有球都装进了瓶子不多不少。2.2 为什么“装完后要回头清货架”是关键假设到货序列是 2、1、3货架容量为 1。处理过程如下先拿到 2不是当前需要的 1放上货架再拿到 1正好装瓶need变成 2此时货架顶上正好是 2取下来装need变成 3最后拿到 3装瓶成功。如果把“装完后回头清货架”这一条忘掉直接处理下一个球那结果就是2 被放上货架1 被装瓶3 被装瓶最后need3已经满足看似成功但实际上货架上还压着一个 2 没装彩虹瓶少了一层而程序却错误地输出了 YES。这样的判题结果必然是 WA答案错误而且不容易想到原因。2.3 正确性的直觉证明为什么这套规则保证最优因为need是递增的不可能回头。如果一个球不等于need在need变成它的编号之前它永远不能装瓶只能暂时放在货架上货架只有 M 个位置所以放着放着满了就必然失败。反过来如果有球能装但工人故意不装、先去动后面到货的球那只会让情况更糟不会更好。所以这个贪心式模拟就是最直接、最标准的解法。3. 动手实现完整代码与关键细节讲解完思路直接上代码。我用 C 写因为判题环境里 C 的栈操作最直观而且内存控制可以做到很干净。3.1 完整可运行的 C 代码#include cstdio #include stack using namespace std; int main() { int n, m, k; scanf(%d %d %d, n, m, k); while (k--) { stackint shelf; int need 1; bool ok true; for (int i 0; i n; i) { int x; scanf(%d, x); if (!ok) { // 已经失败但必须继续读完当前序列剩余数字 continue; } if (x need) { need; // 关键装完一个球后立刻检查货架顶部 while (!shelf.empty() shelf.top() need) { shelf.pop(); need; } } else { // 不是当前需要的球只能放货架 if ((int)shelf.size() m) { ok false; } else { shelf.push(x); } } } printf(ok need n 1 ? YES\n : NO\n); } return 0; }这段代码可以直接在 PAT、PTA 或大部分在线判题系统上通过。核心长度不到 40 行逻辑也不绕但注释里标出的那几行少了任何一处都可能导致误判。3.2 逐段拆解每一行在做什么第一行while (k--)接受测试数据组数每组数据独立判断。注意如果输入存在多组k用完就结束不会有多余输出。stackint shelf定义一个空栈代表货架。每次新序列都要重新定义不能复用上一组的残留数据否则会把上一组遗留下来的球带进下一组判断直接错乱。int need 1从第一层开始装。这是整个模拟的“指针”它指向的是下一层需要装的球编号。for (int i 0; i n; i)每组数据恰好有 N 个球的编号循环处理每个球。内部先判断if (!ok)分支。这一行是保证输入完整性的关键后面第 4 节我会用实际测试数据演示。if (x need)分支当前到货的球正是需要的球装瓶need然后回到循环顶部继续取下一个球。但这里有一个容易漏掉的while循环——装完球后货架顶部可能正好是更新后的need这个循环就是不停地把“能装的都装掉”。因为货架顶端一个接一个取每取一次need就变大一次所以必须用循环而不是if。比如货架从顶到底依次是 4、3、2而你刚装完 1那么一个if只够取掉 23 和 4 就永远留在货架上判题结果就错了。else分支x不等于need此时没有别的选择只能放货架。但在放之前要检查货架是否已经满了。容量是m栈的大小可以通过shelf.size()获取和m比较。这里有一个细节m作为输入读取时是intshelf.size()返回无符号类型无符号数和有符号数比较时可能有隐式类型转换的风险最好把shelf.size()转成int再比较也就是代码里写的(int)shelf.size()。虽然大多数环境里m不大不会出问题但这种习惯能帮你少踩一个平台差异的坑。判断失败后把ok置为false。注意这里我没有continue而是让循环继续跑因为ok false后下一轮循环顶部就会直接continue跳过所有逻辑。如果我在置false后立刻continue那当前这层循环里剩下的代码也不会执行其实等价但容易造成逻辑顺序不清晰我习惯只在顶部统一处理。3.3 复杂度分析为什么这题没有性能压力每个球最多被处理两次一次是从输入中读入并判断一次是可能被压入货架后再弹出来。循环while里的弹栈操作每弹一次对应一次入栈所以总操作次数是 O(N) 级别。加上每一组数据的初始化复杂度 O(kN)其中 k 是测试组数。N 在题目范围内通常只有几百所以这个算法很快压根不用考虑优化的问题。就算 N 放大到十万栈模拟的思路依然能跑得动。4. 容易踩的坑与调试技巧这题逻辑看起来短实际提交时 WA 的人不在少数。我把常见的坑按“栽跟头顺序”整理了一下。4.1 失败后没有把剩余数字读完这是我最想提醒的一个问题。假设输入是3 2 2 3 1 2 2 3 1第一组数据n3m2。序列是 3 1 2。处理过程拿到 3不等于 1放货架拿到 1装need2货架顶是 3不等于 2继续读下一个球拿到 2正好装need3结束needn1输出 YES没问题。但如果换一个序列比如 1 3 2同样 n3 m2处理过程拿到 1装need2拿到 3不等于 2放货架此时货架有 1 个球没满拿到 2装need3结束后货架顶上正好是 3但循环已经结束弹掉 3need4最终 YES。现在假设一个失败的序列3 2 1m1。处理过程拿到 3不等于 1要放货架。货架容量 m1当前货架为空可以放。拿到 2不等于 1要放货架。货架已经满了所以失败okfalse。此时还剩下一个球 1 没读。如果程序在置okfalse后就continue跳出循环那么 1 这个数就不会被读走。下一组数据的第一个数就会读到 1导致后续判断全部错乱序列变成 1、2、3 之类本来可能失败的案例被判成 YES本来成功的案例被判成 NO。解决办法就是顶部那个if (!ok) continue;保证序列在失败后仍然能完整读完不影响下一组数据。4.2 把“检查货架顶”写成了if而不是while我见过不少同学写出这样的代码if (x need) { need; if (!shelf.empty() shelf.top() need) { shelf.pop(); need; } }这个写法只处理了货架最顶上的一个球。假设货架从上到下依次是 3、2而你刚装完 1那么need更新为 2此时货架顶是 3不是 2这个if不会执行。但货架里明明还有 2 可以装只是被 3 压住了。然而这个场景真的会出现吗如果货架从上到下是 3、2说明 3 比 2 更晚被放入货架那么 2 是被先放入的。当 2 刚被放入时need是多少呢如果当时need 2那么 2 永远不会被需要最终一定失败。换句话说出现这种“下面压着更小数”的情况本身已经注定要失败。所以在这种题面下理论上不会出现“下面有可装的但顶部挡着”的情况。但问题在于运行时数据不一定按这个推理来。比如中途有球直接从传送带装瓶没有进过货架那么货架上可能残留一些该装但被其他球压住的情况。更稳妥、更简洁的做法还是统一用while检查因为它的逻辑是“只要顶部能装就一直装”不会漏也不会多装。用if的潜在风险在于如果你先处理了某些直接到货的球导致need连续变了好几次货架顶部像剥洋葱一样一个接一个能装那if就只剥掉最外面一层后面的就全烂在货架里了。4.3 货架容量判断的位置有的版本会在“开始处理之前”就检查货架是否已满这也没错但有个顺序细节要考虑清楚如果一个球x满足x need它是不需要上货架的即使货架满了也没关系因为根本不会往货架上放。所以容量检查必须放在else分支里也就是“确实要放货架”的时候才检查。如果你把容量检查放在循环开头那就会出现“货架满了但这个球可以直接装瓶结果被误判失败”的 bug。4.4 用几组样例快速自测写完代码别急着交先手算几组数据测一测。我最常用的是这几组NM序列预期结果原因311 2 3YES全都直接装货架根本没用到312 1 3NO先来 2不上货架就没地方放货架满后 1 无法处理322 1 3YES2 放货架1 装再取 2 装3 直接装423 1 2 4NO3 放货架1 装2 装但 4 来时 3 仍在货架顶4 无法装同时第三层需要 3货架顶是 3 没错但 4 不能被放到货架顶因为货架满了423 2 1 4NO3、2 依次上货架1 来时装装完后货架顶 2 可装再取 3 装最后 4 直接装应该 YES 才对这里用来检查是否漏了 while我建议你照着这五组数据手工推一遍再把代码跑一遍。前四组能查基础逻辑第五组专门查“装完一个球后货架顶上是否还有连续可装的球”。如果你的输出和预期不一样那你基本已经知道问题出在哪一段了。5. 从彩虹瓶看开去这个模型能用在哪很多人刷题止步于“AC 了就完”但多做一步思考其实收获更大。彩虹瓶本质上是一个“乱序输入 有限容量栈缓存 顺序输出”的问题。这个模型在真实场景里相当常见。比如操作系统的任务调度多个进程按某种顺序请求 CPUCPU 只有有限数量的内核可用相当于容量受限的“货架”新到的任务如果暂时不能执行就得排队等待。再比如仓库的“后进先出”库存管理货物按一定顺序入库但出库却必须按另一套规则容量有限这时候是否能够顺利把货全部出完正好可以用这种栈模拟来验证。还有浏览器后退按钮的实现原理本质上就是历史记录栈你浏览 A 页面然后跳到 B再跳到 C点击后退时先回到 B再回到 A先进后出和货架取球一模一样。如果中间被迫清空历史记录类似于货架满了某些页面就无法返回了。所以这道题真正的价值不只是拿 20 分而是帮你培养一种“看到操作规则先判断数据结构”的思维习惯。拿到一道描述很复杂的题第一反应不是“怎么模拟”而是“这里的操作本质是什么结构”。看到“只能从顶部取”、“放也只能放顶部”、“容量有限”栈的形象就立刻立起来了后面写代码只是顺水推舟的事。6. 一点个人体会我印象最深的一次是在本机上测试了好几个样例都输出正确结果提交上去还是 WA。后来一行行对才想起来忘了写“失败后继续读完剩余数据”这个处理。当时测数据写的都是第一组就失败的用例没考虑到这组失败以后后面组次的数据会被吞掉导致错位。从那以后我再遇到这类“一组数据由多个 case 构成”的题都会习惯性地把“当前 case 失败时如何跳过剩余输入”这部分先写好再写主要逻辑。这算是做题习惯上的一个收获吧。另外再分享一个写这类模拟题的小技巧不要急着堆代码先把“需要维护哪些状态”列出来。彩虹瓶这题就两个状态need和栈shelf想清楚这两个状态分别在哪些操作下变化代码自然就写出来了。如果你把状态列出来发现自己有第四个、第五个变量那多半说明思路还没化简到最简得停下来重新想一想。这 20 分不难拿但拿到之后的总结才是真正拉开差距的地方。