B3630 排队顺序这道题我前后交了三版代码才把分拿满说起来有点丢人——第一版我照着输入顺序直接输出了编号第二版把「身后」当成了「身前」直到第三版才老老实实去想「谁站在队头」这个事儿。这道题属于典型的看着简单、动手就翻车的类型题面短得只有两句话但里面藏着的链式思维恰恰是后面学链表、学拓扑排序、学图遍历时反复要用的东西。如果你刚摸到数组和循环它是一道很好上手的手感题如果你已经刷了几十道它也是一道值得回头琢磨「有没有更省空间的写法」的小题。下面我把自己从读错题到写出四种解法、再到踩遍坑的全过程摊开讲你能直接抄的代码、能直接避的坑我尽量都写清楚。1. 先把题目读懂一条链藏在输入里1.1 题面在说什么每个数字都是一句「我后面是谁」这道题题号 B3630题名「排队顺序」的设定大概是这样的有 n 名同学排成一列编号从 1 到 n每个人只知道一件事——自己身后站的是谁。现在把这 n 个人的「身后信息」按编号顺序丢给你第 i 个数表示编号为 i 的同学身后那位同学的编号如果这个数是 0说明这位同学后面已经没人了他就是队尾。你要做的就是把这支队伍从队头到队尾完整还原出来。说明不同版本的题面在输入细节上可能略有出入比如是否单独一行、0 还是 -1 表示队尾我这里按最常见的那一版展开你拿到题之后最好先自己核对一遍输入格式和结尾标记这类细节搞错是最冤的丢分方式。理解这个设定之后你会发现整支队伍其实是一根单向的链条A 后面是 BB 后面是 CC 后面没人——那队伍就是 A、B、C。输入给你的不是「队伍顺序」而是一堆「相邻关系」你要做的是把这些散落的边重新串成一条链。这跟拼图是一个道理每一块只告诉你「我右边是哪块」你得先找到最左边那块才能一块一块拼下去。1.2 新手最容易误读的地方输入顺序不等于队伍顺序我第一次做这题时犯的错估计也是大多数人第一次会犯的看到输入给了 n 个数就以为按顺序输出就完事了。为什么错因为输入的下标是「人的编号」而题目要的输出是「队伍中的位置」这两个顺序完全不是一回事。举个具体例子你就明白了。假设 n 4输入是2 4 0 3。这串数字的意思是1 号后面是 2 号2 号后面是 4 号3 号后面没人4 号后面是 3 号。真正的队伍是 1 → 2 → 4 → 3输出应该是1 2 4 3。如果你直接输出1 2 3 4或者输出2 4 0 3都是错的。我第一版就是栽在这儿样例都没过就开始怀疑人生。所以做题的第一步永远是把输入里的每个数字翻译成人话逐条念出来「编号为 i 的人后面站的是 a[i]」。念一遍你就知道该干什么了。这个习惯在后面做图论题时更要命一条边到底是「i 到 j」还是「j 到 i」方向搞反整个算法就废了。1.3 数据规模决定了你能不能用笨办法这类排队还原题的 n 通常在 10 万量级个别版本会拉到 100 万。这个规模意味着什么意味着你写个双层循环去「每次从头扫描找队头」的 O(n²) 做法10 万的数据就是 100 亿次操作一秒内绝对跑不完直接超时。我在纸上算过一笔账假设评测机每秒能做 1 亿次简单运算10 万规模的平方是 10¹⁰也就是 100 亿理论上要 100 秒。哪怕常数再小也差了两个数量级。而 O(n) 的写法10 万次操作连一毫秒都用不到。所以这题的正确姿势必须是一次遍历建表、再一次遍历输出总共两趟谁都别想多绕一圈。这也是我后来养成的一个习惯看到 n 是 10⁵ 起步先在脑子里过一遍「哪些操作是 O(n)、哪些是 O(n log n)、哪些是 O(n²)」把平方级的想法直接掐死省得写完才发现方向错了。2. 核心思路拆解队头是唯一的突破口2.1 为什么「队头」是最先要找到的东西链条只能从头往后走这是它的物理性质决定的。输入给你的信息是「我后面是谁」全都是往后的方向没有任何人告诉你「我前面是谁」。所以你站在队伍中间任何一个人身上都没法往回走只能顺着往下滑。想完整走完整条链起点必须是那个前面没有人的人也就是队头。我用一个生活场景打比方你手里有一串钥匙每把钥匙上都贴着一张纸条写着「下一把钥匙的样子」但没有任何一把写着「上一把是谁」。你想把所有钥匙串起来唯一的办法就是先找出那把从来没被别人「预告」过的钥匙——它就是第一把。具体到这道题队头的判定条件非常干脆在所有 a[i] 的值里从来没有出现过的那个人就是队头。因为只要有人在你前面他的 a 值就会等于你的编号你就会出现在这堆数字里。反过来从头到尾没被提到过的编号前面必定空着他就是队头。队尾同理a[i] 0 的那个人就是队尾。2.2 用标记数组把「没出现过的人」圈出来思路有了怎么实现最直白的做法是开一个布尔数组hasPrev[]含义是「这个人前面有人吗」。读入的时候每读到一个 a[i]只要它不是 0不是队尾就把hasPrev[a[i]] true。全部读完从 1 到 n 扫一遍第一个hasPrev[i] false的就是队头。这个做法的好处是逻辑极其清楚不需要任何脑筋急转弯写出来自己看着都放心。数组大小开 n 5 就够多出来的几个位置是给自己留缓冲防止下标算错的时候直接踩到别人内存上。这个「多开几个」的习惯我从学数组那会儿就养成了虽然看着土但确实救过我不少次。有一点要特别注意标记的时候必须判断a[i] ! 0。因为 0 不是一个真实的人它只是个「没人了」的暗号如果你不加判断地把hasPrev[0]设成 true虽然不会影响结果你扫的是 1 到 n但如果后面写成了从 0 开始扫就容易出幺蛾子。这种「边界值当成真实数据处理」的失误属于典型的手滑型 bug很难靠肉眼看出来。2.3 四种等价写法从「好懂」到「好省」标记法不是唯一解。我后来折腾出了四种写法各有各的适用场景摆在一起对比一下你就明白该选哪个写法核心操作时间复杂度额外空间适合场景布尔标记法标记每个被指向的编号O(n)n 个 bool最通用可读性最好首选前驱数组法记录 pre[后继] 前驱O(n)n 个 int需要顺带求「谁在我前面」时顺手写入度统计法统计每个编号被指向次数O(n)n 个 int想跟拓扑排序的思路对齐时总和相减法1..n 求和减去所有非零 a[i]O(n)0内存卡得死、或者想炫技时前驱数组法值得多说一句读入a[i] j时顺手写pre[j] i读完以后pre[i] 0的就是队头。这个写法的妙处在于你同时拿到了反向信息如果题目后来改问「队伍倒过来输出」你直接拿 pre 数组就能走不用重写。总和相减法是我个人最喜欢的一个小花招原理很简单队头是所有编号里唯一没在 a 数组中出现过的那个那么 1 到 n 的总和减去所有非零 a[i] 的和剩下的不就是队头吗一行代码搞定连数组都不用开。但这里有个坑要提前说n 到 10 万时总和能到 5×10⁹早就超过 32 位整型的范围了必须用 64 位整数C 里的long longPython 不用管。我第一次写这个的时候用的是 intn 一到 10 万直接溢出成负数输出个负号查了半小时才发现是自己挖的坑。还有一个更骚的异或法把 1 到 n 全部异或起来再异或上所有非零的 a[i]剩下的就是队头。原理跟总和法一致但好处是不会溢出因为异或的结果永远在数值范围内。缺点是可读性差别人看你的代码得反应三秒。这种写法我只在比赛里赶时间时用过平时写题解还是老老实实用标记法。3. 手把手实现从读入到输出3.1 数组怎么开、下标从哪里开始数组开法这件事看起来是小事实际上是新手翻车的高频区。有几个原则我建议你直接记住第一数据规模往大了开。如果题面说 n ≤ 10⁵那就开到 10⁵ 10多开十个位置的成本几乎为零但能挡住大量越界问题。如果在本地用大数组一定要开成全局变量放在 main 函数外面因为全局区内存大函数内部的栈空间小开个百万元素的数组放栈上很容易直接崩掉报出来的错还是一句莫名其妙的「运行时错误」根本看不出是数组开大了。第二下标从 1 开始用。这题的编号是 1 到 n你要是习惯从 0 开始存那就得在每次读写时做i - 1的偏移多写一次就多一次错的机会。做这种和「编号」强绑定的题我一般直接把数组开到 n 1用下标 1 对应编号 1脑子清爽很多。第三布尔数组默认是 false。C 的全局数组会被自动清零hasPrev一开始全是 false正好符合「一开始假设所有人前面都没人」的初始状态省去手动初始化。但如果你把它定义在函数里就变成随机值了这个细节必须注意。3.2 找队头与沿链遍历的核心循环整个算法的骨架只有两段我把它拆开说。第一段是建表一边读入一边标记。读第 i 个数 a[i] 时做三件事——存进 next 数组、判断它是不是 0、如果不是 0 就把hasPrev[a[i]]标成 true。这一趟下来链表结构和「谁不是队头」的信息全都有了。第二段是走链先扫一遍找到队头 head然后从 head 出发while (cur ! 0)一路打印每次把 cur 更新成next[cur]直到走到 0队尾后面循环结束。这个写法的正确性其实依赖两个题面保证一是整支队伍是一条完整的链不会分叉也不会断二是恰好有一个人前面没人。如果数据不合法比如成环这个 while 会一直转下去程序直接卡死。所以我在写的时候习惯加一个计数器保护走一步加一一旦超过 n 还没结束就说明数据有问题立刻 break 出来。这个习惯在做图论题时更重要因为那里动不动就给你一个环。3.3 完整代码C 与 Python 双版本C 版本我按最朴素的写法来不加任何花活方便你对照着看逻辑#include cstdio const int MAXN 1000005; int nxt[MAXN]; bool hasPrev[MAXN]; int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d, nxt[i]); if (nxt[i] ! 0) { hasPrev[nxt[i]] true; } } int head 0; for (int i 1; i n; i) { if (!hasPrev[i]) { head i; break; } } int cur head; bool first true; int cnt 0; while (cur ! 0 cnt n) { if (!first) putchar( ); printf(%d, cur); first false; cur nxt[cur]; cnt; } putchar(\n); return 0; }几个细节解释一下。first变量是用来控制空格的第一项前面不加空格后面的每项前面补一个最后统一换行。这样写出来的输出格式绝对干净不会出现「最后一个数字后面多一个空格」这种被评测机判定格式错误的情况。cnt n是那个防死循环的保护正常情况下走不到触发条件。Python 版本要注意读入效率。这题 n 大的时候用input()一行行读会明显变慢我一般用sys.stdin.buffer.read()一次性读进来再切分import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) if not data: return n data[0] a data[1:1 n] nxt [0] * (n 2) has_prev [False] * (n 2) for i in range(1, n 1): nxt[i] a[i - 1] if nxt[i] ! 0: has_prev[nxt[i]] True head 0 for i in range(1, n 1): if not has_prev[i]: head i break ans [] cur head cnt 0 while cur ! 0 and cnt n: ans.append(str(cur)) cur nxt[cur] cnt 1 sys.stdout.write( .join(ans)) main()Python 这边我把结果先攒到列表里再一次性join输出这比在循环里不停print快得多。列表append 是 O(1)join 是 O(n)加起来一趟过完10 万的数据量也就几十毫秒。3.4 自造数据验证三种边界用例代码写完别急着交自己造几组数据跑一跑能省掉大量无谓的提交次数。我一般固定测三种第一种最小规模。n 1输入就是0也就是只有一个人而且后面没人。输出应该是1。这组数据专治各种下标越界和初始化为空的问题。我第二次交的那个版本就是在这挂的因为我把队头的搜索写成了从 0 开始结果扫到 hasPrev[0] 是 false直接把 0 当队头输出了。第二种顺序被打乱的中等规模。比如 n 5输入3 5 0 2 4。翻译一遍1 后是 32 后是 53 后没人4 后是 25 后是 4。队伍应该是 1 → 3同时 4 → 2 → 5 → 4不对2 后面是 55 后面是 44 后面是 2这就成环了数据本身不合法。所以我换一组3 5 0 1 2。翻译1 后 32 后 53 后没人4 后 15 后 2。队伍是 4 → 1 → 3还有 5 → 2 独立成链也不对这组数据出现了两条链同样不合法。正确的构造方式是让所有人串成一条比如2 4 0 5 31 后 22 后 43 后没人4 后 55 后 3队伍就是 1 2 4 5 3。提示自己造数据时最容易造出来的就是「两条链」或者「带环」的非法数据。造完先自己手动走一遍确认能串成一条完整的链再拿去测否则测出来的错误是你自己的数据错了白折腾。第三种极端顺序。比如 n 5输入2 3 4 5 0队伍是 1 2 3 4 5这是最顺的情况再来一组0 1 2 3 4意思是 1 号后面没人2 号后是 13 号后是 24 号后是 35 号后是 4队伍是 5 4 3 2 1完全倒过来。这两组能测出你的遍历方向有没有搞反。4. 踩坑实录与排查清单4.1 输出格式的坑空格和换行这类「输出一串数字」的题格式错误比算法错误更常见。评测机对输出的比对是逐字符的多一个空格、少一个换行都会被判错而且报出来的提示往往只是简单的「格式错误」根本看不出是哪里多了个空格。我踩过的坑主要有两个。一个是末尾多空格用printf(%d , x)一路输出最后那个数字后面就带了个尾巴。解决办法就是我上面代码里的first标记法或者干脆先把结果存进数组最后用join拼起来。另一个是没有输出换行有些评测机对这个不敏感有些就卡你为了稳妥最后统一补一个putchar(\n)成本为零。还有一种更隐蔽的如果 n 比较小你可能不小心在数字之间打了两个空格肉眼根本看不出来。这种问题只能靠把输出重定向到文件里用编辑器的「显示空白字符」功能去看。我现在的习惯是写完输出部分先在本地跑一遍样例把输出粘到文本编辑器里开可见空白确认一遍再交。4.2 下标混用和数组越界下标问题几乎每道题都会遇到这题尤其容易出。因为题目里的编号是 1 到 n而很多人习惯数组从 0 开始于是代码里就出现了a[i - 1]和a[i]混着用的情况改到后面自己都不知道自己在写啥。我的处理方式是全程统一编号是 1 到 n那数组就开到 n 1所有下标都用 1 到 n一次偏移都不做。只有在 Python 里从data列表切片的时候才需要减一而且我把这一步单独拎出来写在一行里注释清楚避免后面再碰。数组越界这个更危险因为它的表现很不稳定。有时候程序正常跑完有时候直接崩有时候悄悄改掉了别的变量的值让你在完全无关的地方看到诡异的错误。最典型的场景是hasPrev[nxt[i]] true这一句如果nxt[i]读进来的值比 n 还大数据有误或者读错了这一句就越界了。所以数组多开十个位置这个习惯真不是迷信。4.3 死循环数据不合法时怎么办按题面保证输入一定是一条合法的链理论上不会成环。但实际做题时你可能会因为读错格式、数组没清空、或者上一组数据的残留导致程序走进一个环里出不来。表现就是程序不输出也不结束本地跑的时候一直转交上去就是「运行超时」。我的应对方法是永远加一个计数器。不管题目保证得多好走链的循环里我都写cnt n这个条件一旦超过 n 步还没走到头说明要么数据有环要么我的 next 数组构造错了两种情况都该立刻停下。配合在本地调试时打印一下走到哪一步断的问题很快就能定位。另外一个小技巧本地测试时如果怀疑某组数据有问题可以先把 next 数组完整打印出来人工核对一遍「每个人后面是谁」有没有对上。这一步看起来很笨但对于长度只有十几的测试数据比盯着代码看快多了。4.4 常见问题速查表下面这张表是我把自己和身边人踩过的坑整理出来的做题时对不上结果可以挨个排查现象最可能的原因排查方法输出为空或只有一个 0队头没找到head 保持初值 0检查 hasPrev 标记时有没有漏判a[i] ! 0输出顺序整体反了把「身后」理解成了「身前」重新翻译一遍题面确认 a[i] 的含义只输出了一部分人就停了链在中间断掉了打印 next 数组看哪个位置的值异常程序一直不结束数据成环while 出不来加上计数器上限超过 n 就跳出最后一个点总是错输出末尾多了空格或没换行用 first 标记控制分隔符末尾统一换行大数据的点答案离谱求和法用了 32 位整数溢出改用 64 位整数或换成异或法本地能过、提交报运行错误大数组开在函数栈上把数组改成全局变量Python 版本超时用了 input() 逐行读换成 sys.stdin.buffer.read() 一次读入5. 做完这道题还能顺手练什么5.1 换个方向如果题目给的是「前面是谁」这题最值得做的变形就是把输入的含义反过来每个 a[i] 表示的是「编号 i 的同学前面站的是谁」。这时候你手里握着的全是往前的信息从任何一个人出发都能往回走但没法往前走。怎么办答案很简单从队尾出发一路往前收收完把整个序列倒序输出。队尾的判定条件也变了变成「从来没在 a 数组里出现过的那个编号」。这个变形我练过几次看着只是方向反了一下但如果你不假思索地套原题的代码就会输出一个完全颠倒的队伍而且样例可能还过得去有些样例正好对称交上去才发现全错。这个练习的价值在于让你意识到链是有方向的方向决定你从哪头切入。这个思维在后面做有向图遍历、做依赖关系分析时天天要用。5.2 从一条链到一张网这题其实是拓扑排序的入门特例如果你学过拓扑排序回头再看这道题会有种恍然大悟的感觉。拓扑排序处理的是「有依赖关系的任务排序」每个任务可能有多个前置而这道题里每个人最多只有一个前置站在他前面的人和最多一个后继是一张退化成链的图。所以这题的所有操作在拓扑排序里都有对应找队头 找入度为 0 的点沿链走 按拓扑序输出标记 hasPrev 统计入度。你甚至可以把这题的代码直接改写成拓扑排序的骨架只把「每个点只有一个出边」这个限制去掉就变成了一个通用的拓扑排序实现。我建议你在做完这题之后去找一道真正的拓扑排序题对比着看你会发现两者的骨架几乎一模一样差别只在于一个是单后继数组就够一个是多后继需要邻接表。这种「从一个特例看到一类问题」的跳跃是刷题效率提升最快的阶段。5.3 输入输出习惯的沉淀最后说点题外的但我觉得比算法本身更值钱。这道题让我彻底改掉了几个坏习惯。一是读入必须考虑规模。以前我不管三七二十一就用cin觉得反正有加速。后来在 n 到 10⁶ 的题上吃过亏才开始分场景小数据随便写大数据一律scanf或者read()一次读入。这个判断现在已经是肌肉记忆了。二是输出必须检查格式。以前我觉得「差不多就行」直到被格式错误卡了三次才开始养成「末尾不留空格、结尾必有换行」的固定写法。现在我的输出部分基本是模板化的先攒结果再统一输出几乎不会再出格式问题。三是写完必须自造数据。样例只能证明你理解了题面证明不了你的代码是对的。最小规模、打乱顺序、极端顺序这三组数据我现在是雷打不动要跑的跑完再去提交通过率明显上来了。这道题本身难度不高但把这几个习惯固化下来之后我后面做中等题的调试时间至少缩短了一半。有时候一道水题的价值不在于它考了什么算法而在于它逼你把基本功练扎实了。