企业官网建设流程全解析

我翻到这道“彩虹瓶”的时候，第一反应是：这不就是个模拟题嘛，按流程走一遍完事。但真正上手写代码之后我才发现，这题把栈的两个核心特性——先进后出和容量受限——考得非常细。尤其是“装好一个球之后，必须回头检查货架顶上的球能不能继续装”这一步，逻辑漏掉一半，判题结果就是一片红。

这题的场景其实很生活化：工厂按编号顺序生产彩色球，彩虹瓶也要按编号顺序装填，但送货顺序会被打乱，工人又不能把球扔到一边不管，只能放到一个容量有限的货架上暂存。说白了就是一个“队列生产、栈式缓存、顺序消费”的模拟题，数据结构基础扎实的人三分钟能写完，但没理解透栈的“只能在顶部操作”这个限制的人，会反复栽在同一个坑里。

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 被装瓶，最后need=3已经满足，看似成功，但实际上货架上还压着一个 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--) { stack<int> 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用完就结束，不会有多余输出。

stack<int> 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只够取掉 2，3 和 4 就永远留在货架上，判题结果就错了。

else分支：x不等于need，此时没有别的选择，只能放货架。但在放之前要检查货架是否已经满了。容量是m，栈的大小可以通过shelf.size()获取，和m比较。这里有一个细节：m作为输入读取时是int，shelf.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

第一组数据：n=3，m=2。序列是 3 1 2。处理过程：拿到 3，不等于 1，放货架；拿到 1，装，need=2；货架顶是 3，不等于 2，继续读下一个球；拿到 2，正好，装，need=3；结束，need==n+1，输出 YES，没问题。

但如果换一个序列，比如 1 3 2，同样 n=3 m=2，处理过程：拿到 1，装，need=2；拿到 3，不等于 2，放货架，此时货架有 1 个球，没满；拿到 2，装，need=3；结束后货架顶上正好是 3，但循环已经结束，弹掉 3，need=4，最终 YES。

现在假设一个失败的序列：3 2 1，m=1。处理过程：拿到 3，不等于 1，要放货架。货架容量 m=1，当前货架为空，可以放。拿到 2，不等于 1，要放货架。货架已经满了，所以失败，ok=false。此时还剩下一个球 1 没读。如果程序在置ok=false后就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 用几组样例快速自测

写完代码别急着交，先手算几组数据测一测。我最常用的是这几组：

我建议你照着这五组数据手工推一遍，再把代码跑一遍。前四组能查基础逻辑，第五组专门查“装完一个球后，货架顶上是否还有连续可装的球”。如果你的输出和预期不一样，那你基本已经知道问题出在哪一段了。

5. 从彩虹瓶看开去：这个模型能用在哪

很多人刷题止步于“AC 了就完”，但多做一步思考其实收获更大。彩虹瓶本质上是一个“乱序输入 + 有限容量栈缓存 + 顺序输出”的问题。这个模型在真实场景里相当常见。

比如操作系统的任务调度：多个进程按某种顺序请求 CPU，CPU 只有有限数量的内核可用，相当于容量受限的“货架”；新到的任务如果暂时不能执行，就得排队等待。再比如仓库的“后进先出”库存管理：货物按一定顺序入库，但出库却必须按另一套规则，容量有限，这时候是否能够顺利把货全部出完，正好可以用这种栈模拟来验证。

还有浏览器后退按钮的实现原理，本质上就是历史记录栈：你浏览 A 页面，然后跳到 B，再跳到 C，点击后退时先回到 B，再回到 A，先进后出，和货架取球一模一样。如果中间被迫清空历史记录（类似于货架满了），某些页面就无法返回了。

所以这道题真正的价值不只是拿 20 分，而是帮你培养一种“看到操作规则，先判断数据结构”的思维习惯。拿到一道描述很复杂的题，第一反应不是“怎么模拟”，而是“这里的操作本质是什么结构”。看到“只能从顶部取”、“放也只能放顶部”、“容量有限”，栈的形象就立刻立起来了，后面写代码只是顺水推舟的事。

6. 一点个人体会

我印象最深的一次，是在本机上测试了好几个样例都输出正确，结果提交上去还是 WA。后来一行行对才想起来，忘了写“失败后继续读完剩余数据”这个处理。当时测数据写的都是第一组就失败的用例，没考虑到这组失败以后，后面组次的数据会被吞掉，导致错位。从那以后，我再遇到这类“一组数据由多个 case 构成”的题，都会习惯性地把“当前 case 失败时如何跳过剩余输入”这部分先写好，再写主要逻辑。这算是做题习惯上的一个收获吧。

另外再分享一个写这类模拟题的小技巧：不要急着堆代码，先把“需要维护哪些状态”列出来。彩虹瓶这题就两个状态，need和栈shelf，想清楚这两个状态分别在哪些操作下变化，代码自然就写出来了。如果你把状态列出来发现自己有第四个、第五个变量，那多半说明思路还没化简到最简，得停下来重新想一想。这 20 分不难拿，但拿到之后的总结，才是真正拉开差距的地方。