第一次在洛谷上看到 P1160 这道“队列安排”很多人第一反应都是“这不就是数组插插删删最后输出一下吗”然后高高兴兴用 vector 写完一提交超时。再回头看一眼数据范围n 和 m 都是十万级别vector 的 insert 和 erase 在中间操作是 O(n) 的最坏情况下每次插入都要挪动上万个元素总复杂度直接爆炸到 10^10 级别TLE 一点都不冤。这题真正考的其实不是“队列”而是“链表”——准确点说是用数组模拟双向链表把每次插入和删除都压到 O(1)。今天我就把这个思路从头到尾拆一遍把完整 AC 代码、指针修改顺序、还有几个我当年踩过的坑都拿出来说说。不管你是刚开始刷洛谷的新手还是已经会链表但老在细节上 WA 的同学这篇应该都能帮到你。1. 题目到底在干什么先把“队列安排”啃透1.1 输入格式与操作拆解题目流程是这样的一开始队列里只有 1 号同学。接下来 2 号到 n 号同学依次入队每次输入两个整数 k 和 p意思是把当前编号为 i 的同学插到编号为 k 的同学左边p0或者右边p1。注意输入的第 i 行对应的是 i 号同学这行里的 k 一定小于 i也就是说参照对象一定是已经入队的同学。插入全部完成后再输入一个整数 m接下来有 m 行每行一个整数 x表示把 x 号同学从队列中移走。如果 x 已经不在队列里就忽略这次操作。最后要求按从左到右的顺序输出还在队列里的同学编号。这就是一个典型的“中间插入 任意删除 顺序输出”问题。关键在于 n 和 m 都可以到 100000如果用普通数组存队列插入到中间位置就得把后面所有元素整体后移删除也一样单次操作最坏 O(n)算上 n-1 次插入和 m 次删除整体复杂度是 O((nm)×n)拿 1e5 的数据去跑基本没有活路。1.2 为什么数组直接搞不定有人可能会说“我用 vector 的 insert 和 erase 不就行了”vector 的 insert 在头部或中间插入确实会帮我们移动元素但它底层仍然是数组拷贝复杂度是 O(n)。假设每次都往队头插第二次插入要挪 1 个元素第三次要挪 2 个……到第 n 次要挪 n-2 个累计下来就是 O(n²)。这还只是插入后面还有 m 次删除删除中间元素同样要搬移。所以这道题的本质就是要在一个序列中频繁地“知道某个编号的左右邻居是谁并修改它们”这正是链表的天然优势。但 C 语言的 struct 链表需要动态分配节点写起来啰嗦还容易内存泄漏C 的 STL list 虽然能用但竞赛里用它维护“按编号删除”还得额外存迭代器代码反而不清爽。于是就有了最经典的解法用两个数组 l[i] 和 r[i] 分别记录编号 i 左边和右边的人用 0 表示空。这就是“数组模拟双向链表”。2. 核心思路用数组模拟双向链表O(1)完成插入和删除2.1 为什么选“前驱/后继”数组而不是 STL list我先说说为什么不直接用 list。STL 的 list 确实是双向链表插入删除也是 O(1)但它的问题是节点动态分配常数大而且题目要求按编号删除某个同学如果用 list 的迭代器来定位节点则需要额外维护一个迭代器数组 iter[i]删除的时候才能 O(1) 找到对应节点。否则你还得从 head 开始遍历找编号那样删除一次就是 O(n)。相比之下数组模拟双向链表是这样的l[i] 表示编号 i 左边同学的编号没有则为 0r[i] 表示编号 i 右边同学的编号没有则为 0vis[i] 记录编号 i 是否已经被删除。这样我们不仅能用 O(1) 找到任意编号的左右邻居还能直接用编号访问节点不需要遍历查找。这种静态链表的方式内存连续cache 友好实际运行速度比 STL list 快很多代码也更好调试。2.2 插入操作的推导先接新节点再拆旧连接假设当前编号为 i 的同学要插入到编号为 k 的同学左边。也就是说i 会成为 k 的左邻居。设原来 k 的左邻居是 L l[k]那么插入后i 的右边是 ki 的左边是原来的 L如果 L 不为 0那么 L 的右边要变成 ik 的左边要变成 i。写成代码就是l[i] l[k]; r[i] k; if (l[k]) r[l[k]] i; l[k] i;注意这里有个很关键的细节如果 k 原来没有左邻居也就是 l[k] 0说明 k 是当前队列的队头那么 i 插入后就会成为新的队头。所以当 l[k] 为 0 时我们还得更新 head 为 i。再来看插入到 k 的右边。设 k 原来的右邻居是 R r[k]那么插入后i 的左边是 ki 的右边是原来的 R如果 R 不为 0那么 R 的左边要变成 ik 的右边要变成 i。代码l[i] k; r[i] r[k]; if (r[k]) l[r[k]] i; r[k] i;插入到 k 的右边不会改变队头因为队头始终是最左边的元素而新节点插在了 k 的右边。这里有一个非常容易踩的雷修改指针的顺序。如果你先写 r[k] i再取原来的 r[k]那原来的右邻居就丢了。所以一定不要提前破坏老节点的指针。我自己的口诀是“先让新节点 i 的前驱后继指向正确再修正老节点的连接”。2.3 删除操作的正确姿势删除编号为 x 的同学时如果 vis[x] 已经为 true说明这个人早就被删过了直接忽略。否则先记录它的左邻居 L l[x]右邻居 R r[x]。删除的本质就是让 L 和 R 直接相连让 x 从链表中脱离如果 L 不为 0那么 L 的右边变成 R如果 L 为 0说明 x 是队头删除后队头变成 R如果 R 不为 0那么 R 的左边变成 L标记 vis[x] true。代码if (vis[x]) continue; int L l[x], R r[x]; if (L) r[L] R; else head R; if (R) l[R] L; vis[x] true;这里不需要修改 x 自己的 l[x] 和 r[x]因为它已经不在链表里了之后只要保证不会再次访问它就行。2.4 如何确定队头和最终输出由于数组模拟链表没有一个“总起点”我们必须用一个变量 head 记录当前最左边的人是谁。初始时 head 1因为队列里只有 1 号。插入时只有当“把新节点插入到某个节点的左边且这个节点本来就是队头”时head 才会被更新成新节点。插入到右边永远不改变 head。删除时如果删除的节点是队头head 就要变成它的右邻居如果删除的不是队头head 不变。最后输出时只需要从 head 开始一路沿着 r[cur] 遍历到 0 为止即可得到从左到右的完整队列。这里补充一个更省心的技巧可以引入一个 0 号哨兵节点让 0 始终作为虚拟队头它的右边是真正队头。这样“更新队头”的操作就统一变成“修改 r[0]”不需要在插入和删除里特判 head。实际编码时哨兵写法往往更简洁不容易漏条件。下面我会给出一个带哨兵版本的代码方便对比。3. 代码实现从零写完并 AC3.1 无哨兵版用 head 变量维护队头下面这版是很多人的首选写法逻辑直观没有额外哨兵#include bits/stdc.h using namespace std; const int MAXN 100005; int l[MAXN], r[MAXN]; bool vis[MAXN]; int main() { int n; scanf(%d, n); // 初始只有 1 号 l[1] r[1] 0; int head 1; for (int i 2; i n; i) { int k, p; scanf(%d%d, k, p); if (p 0) { // 将 i 插到 k 的左边 l[i] l[k]; r[i] k; if (l[k]) { r[l[k]] i; } else { head i; // k 本来是队头i 变成新的队头 } l[k] i; } else { // 将 i 插到 k 的右边 l[i] k; r[i] r[k]; if (r[k]) { l[r[k]] i; } r[k] i; } } int m; scanf(%d, m); while (m--) { int x; scanf(%d, x); if (vis[x]) continue; int L l[x], R r[x]; if (L) { r[L] R; } else { head R; // 删除的是队头 } if (R) { l[R] L; } vis[x] true; } for (int cur head; cur ! 0; cur r[cur]) { printf(%d , cur); } printf(\n); return 0; }这个代码在洛谷上可以直接 AC。唯一的小问题是输出时会多一个末尾空格但洛谷对行末空格不敏感所以没有问题。如果你有洁癖可以先用一个变量统计已经输出的数量在数字之间加空格。3.2 带哨兵版用 r[0] 统一维护队头再贴一个带 0 号哨兵的写法。它的核心思想是让 0 永远作为虚拟队头真正的队头是 r[0]。这样插入到队头左边时我们只需要把 r[0] 更新成新节点删除队头时也只需要修改 r[0]。#include bits/stdc.h using namespace std; const int MAXN 100005; int l[MAXN], r[MAXN]; bool vis[MAXN]; int main() { int n; scanf(%d, n); // 0 作为虚拟头节点初始时队头是 1 l[1] 0; r[1] 0; r[0] 1; for (int i 2; i n; i) { int k, p; scanf(%d%d, k, p); if (p 0) { // 插入到 k 的左边 l[i] l[k]; r[i] k; if (l[k]) { r[l[k]] i; } else { r[0] i; // k 是队头i 成为新的队头 } l[k] i; } else { // 插入到 k 的右边 l[i] k; r[i] r[k]; if (r[k]) { l[r[k]] i; } r[k] i; } } int m; scanf(%d, m); while (m--) { int x; scanf(%d, x); if (vis[x]) continue; int L l[x], R r[x]; if (L) { r[L] R; } else { r[0] R; // x 是队头 } if (R) { l[R] L; } vis[x] true; } for (int cur r[0]; cur ! 0; cur r[cur]) { printf(%d , cur); } printf(\n); return 0; }对比之后你会发现带哨兵版本在“更新队头”这件事上不需要 else 分支里的额外变量赋值代码看起来更统一。我个人的建议是初期练习用无哨兵版可以帮助理解指针变化等你完全理解了再切换到哨兵版能减少很多边界条件的思考成本。3.3 关键代码段逐行解释以无哨兵版为例核心就三步。初始化l[1] r[1] 0; int head 1;1 号同学左右都没有人所以左右指针都是 0。head 是队头初始为 1。插入到左边l[i] l[k]; r[i] k; if (l[k]) r[l[k]] i; else head i; l[k] i;第一步先让 i 的前驱指向 k 原来的左邻居i 的后继指向 k。第二步判断 k 原来有没有左邻居有的话让它的右指针指向 i没有的话说明 k 是队头i 顶替它成为新队头。最后把 k 的左指针指向 i。注意最后一步一定要放在后面因为前面要利用原来的 l[k] 做判断。插入到右边l[i] k; r[i] r[k]; if (r[k]) l[r[k]] i; r[k] i;同理先让 i 的前驱指向 k后继指向 k 原来的右邻居再修改原右邻居的左指针最后把 k 的右指针指向 i。因为插入到右边不会影响队头所以这里不需要更新 head。删除int L l[x], R r[x]; if (L) r[L] R; else head R; if (R) l[R] L; vis[x] true;先用 L、R 把左右邻居存下来防止后续修改相互干扰。如果 x 有左邻居就让左邻居的右边变成 R否则 x 是队头队头变成 R。然后如果 x 有右邻居让右邻居的左边变成 L。最后标记删除。这里之所以先保存 L、R是因为如果 x 是队头head 要赋新值而此时还没有修改 R 的左指针所以顺序不能乱。4. 容易踩的坑WA/TLE 现场复盘4.1 TLE 的元凶vector 的 insert/erase这题最有迷惑性的地方就是题目名字叫“队列安排”所以很多人真用 queue或者 deque。但 queue 只能队头出、队尾入根本没法支持“插到某人左边右边”。deque 虽然支持中间插入但复杂度同样是 O(n)。vector 的 insert 和 erase 更是重量级数据小看起来没问题数据一上 1e5 直接原形毕露。如果拿这题去对比复杂度可以看下面这个表实现方式单次插入单次删除总复杂度nm1e5vector insert/eraseO(n)O(n)O(n²)STL list 迭代器数组O(1)O(1)O(n)但常数较大数组模拟双向链表O(1)O(1)O(n)且常数极小看到 O(n²) 就应该本能地警惕。竞赛里只要看见 n 到 1e5基本就要想 O(nlogn) 或 O(n) 的算法如果出现了 O(n²)那几乎必挂。4.2 指针修改顺序错乱经典 WA很多人第一次写链表插入容易写出类似这样的错误代码r[i] r[k]; l[i] k; r[k] i; if (r[i]) l[r[i]] i; // 这行其实用的还是原来的 r[k]不r[i] 已经保存了原 r[k]所以也行本质上只要先把 i 的左右指针接好再修改老节点就不会丢链。但有人喜欢先改老节点比如先执行 r[k] i然后想通过 r[r[k]] 找到原右邻居这时候 r[k] 已经变成 i 了r[r[k]] 就是 r[i]刚被赋值为原右邻居不一定如果还没赋值就出错。为了避免这种混乱我建议严格按照下面顺序先设置新节点的 l[i] 和 r[i]再修改被插入位置原邻居的指针最后修改 k 的指针。只要这个顺序不乱任何插入都不会丢节点。4.3 插入方向搞反p0 和 p1 写反p0 表示插到左边p1 表示插到右边。写代码时最好先把两种情况在纸上画一下标清楚插到 k 左边i 在 k 前面所以 r[i] kl[i] l[k]插到 k 右边i 在 k 后面所以 l[i] kr[i] r[k]。画出来再写基本不会错。我见过不少人把这两种情况完全写反结果样例能过一提交 WA 得莫名其妙就是因为样例里刚还左右对称。4.4 输出时遇到已删除节点如果你删除后没有正确把左右邻居连接起来或者删除时没有标记 vis输出时从 head 一路向右遍历就可能碰到已经删除的节点。更可怕的是如果删除的节点是队头你没有更新 head输出就会从错误的地方开始甚至死循环。所以删除操作里更新 head 的那一行非常关键。很多 WA 都出在这里。建议写完删除逻辑后自己造一个“删除队头”的测试数据手动跑一遍确认 head 是否正确更新。4.5 数组开小和初始化遗漏N 最大是 100000所以数组至少要开 100005。有些同学喜欢开 l[100000]、r[100000]结果 i 到 100000 时直接越界本地不报错洛谷上 RE。另外l[1]、r[1] 以及 head 的初始化不能漏。多组数据题还需要注意清空 vis但本题只有一组不需要考虑。4.6 忽略删除指令可能重复题目明确说如果 x 已经不在队列中则忽略本次指令。也就是说同一个编号可能被删除两次。如果不加 vis 判断第二次删除时会再次去操作 l[x] 和 r[x]此时它们可能已经被清掉了也可能指向一些奇怪的值最终导致链表结构被破坏。正确做法就是在删除前先判断 vis[x]。这是很多新手容易忽略的点但恰恰是本题一个重要的细节。5. 延伸数组模拟链表在竞赛中的通用性5.1 这个套路还能用在哪数组模拟链表在算法竞赛里几乎是“基础生存技能”绝不止 P1160 这一道题。最典型的应用是图论里的“链式前向星”存图它本质就是用一个 head 数组加 next 数组来模拟邻接链表只不过每个节点存的是边的信息。另一个常见场景是约瑟夫问题用数组模拟环形链表时可以直接通过 nxt[i] 跳转删除时只需修改相邻节点的指针比循环数组方便很多。还有一些“模拟内存分配”“模拟进程调度”之类的题如果用数组模拟链表代码会非常简洁。所以学会这题的数组模拟双向链表不只是会了一道题而是掌握了一种通用的“静态链表”表示法。以后遇到需要 O(1) 插入删除并且节点编号已知的问题你都可以往这个方向想。5.2 如果题目升级插入后还要按排名查询数组模拟链表虽然支持 O(1) 插入删除但有个明显的短板它不支持快速随机访问第 k 个元素。比如题目变成“在插入删除的过程中随时查询当前队列第 k 个编号是谁”链表就无能为力了只能从头开始数每次查询 O(n)。这时候就需要更高级的数据结构了可以用树状数组维护每个位置是否有元素然后二分求第 k 个位置也可以用平衡树Treap/Splay直接维护序列。如果你只是想快速知道“某个人左边是谁、右边是谁”那链表依然是杀手级工具。从这里也能看出P1160 其实是一道很好的“数据结构启蒙题”。它的难度不高但能帮你建立“链表思维”让你意识到数组和链表是两种互补的存储方式各有所长。写在最后的个人体会我当年第一次做这道题时也是上来就 vector 一顿操作样例过了提交 TLE整个人都傻了。后来老老实实打开题解区看到数组模拟链表的思路才恍然大悟原来 O(1) 的插入删除是靠“记录左右邻居”而不是“物理移动元素”。现在我每次遇到“频繁中间插入删除”的题第一反应就是链表如果节点编号范围不大就直接开数组模拟。这个习惯帮我解决了很多看似复杂的问题。最后分享一个小技巧写完链表操作后一定自己手画一张图把每一步指针变化标出来。尤其是指针修改顺序画着画着就明白了。等你真的把这张图画通P1160 的代码就再也不容易写错了。