洛谷 P1160 队列安排 —— 双向链表模拟详解

洛谷 P1160 队列安排 —— 双向链表模拟详解

1. 题目背景与描述

一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $1\sim N$。老师采取如下的方法：

1. 先将 $1$ 号同学安排进队列，此时队列中只有他一个人；
2. $2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；
3. 从队列中去掉 $M$ 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式：第一行一个整数 $N$。第 $2\sim N$ 行，第 $i$ 行包含两个整数 $k,p$，其中 $k$ 为小于 $i$ 的正整数，$p$ 为 $0$ 或者 $1$。若 $p$ 为 $0$，则表示将 $i$ 号同学插入到 $k$ 号同学的左边，$p$ 为 $1$ 则表示插入到右边。第 $N+1$ 行为一个整数 $M$，表示去掉的同学数目。接下来 $M$ 行，每行一个正整数 $x$，表示将 $x$ 号同学从队列中移去，如果 $x$ 号同学已经不在队列中则忽略这一条指令。

输出格式：一行，包含最多 $N$ 个空格隔开的整数，表示了队列从左到右所有同学的编号。

输入输出样例 #1：

输入：
4
1 0
2 1
1 0
2
3
3

输出：
2 4 1

数据范围：对于 $100\%$ 的数据，$1 < M \leq N \leq 10^5$。

2. 问题剖析与解题思路

本题的核心操作是在任意已知位置（某个已入列同学的左边或右边）插入新节点，以及按编号删除任意节点。数据规模达到 $10^5$，要求我们必须在 $O(1)$ 时间内完成单次插入和删除操作。

2.1 为什么不能用数组/vector？

• 若使用 std::vector，在中间插入或删除元素需要 $O(n)$ 的时间搬移后续元素。
• 最坏情况下 $N=10^5$，总操作次数约 $2N$，时间复杂度将达到 $O(N^2)$，无法通过。

2.2 为什么选择双向链表？

• 插入操作：已知插入位置（某个节点的左侧或右侧），双向链表可以在 $O(1)$ 时间内完成插入。
• 删除操作：已知待删除节点的编号，若能 $O(1)$ 定位到该节点，则删除也是 $O(1)$。
• 最终遍历输出：沿着链表从头到尾走一遍即可，$O(N)$。

2.3 数据结构设计

由于 $N$ 最大为 $10^5$，我们采用数组模拟双向链表：

• l[i]：编号为 $i$ 的同学左边的同学编号（前驱）。
• r[i]：编号为 $i$ 的同学右边的同学编号（后继）。
• vis[i]：标记编号为 $i$ 的同学是否还在队列中。

这样做的好处是：通过编号可以直接 $O(1)$ 访问到该节点的前驱和后继，无需像指针链表那样遍历查找。

3. 核心难点与细节处理

3.1 如何初始化？

$1$ 号同学最先入列，此时队列只有他一个人，所以：

l[1] = r[1] = 0;  // 0 表示空

3.2 插入操作的实现——关键点

对于第 $i$ 个同学（$i \geq 2$），给定目标同学 $k$ 和方向 $p$：

• $p = 0$：将 $i$ 插入到 $k$ 的左边。
• $p = 1$：将 $i$ 插入到 $k$ 的右边。

我们以 $p=0$（插入到 $k$ 左边） 为例，详细拆解指针变化：

假设当前队列中有一段：... L <-> k <-> R ...（$L$ 是 $k$ 左边的同学，$R$ 是 $k$ 右边的同学）。

将 $i$ 插入到 $k$ 的左边后，队列变为：... L <-> i <-> k <-> R ...

需要修改四条指针：

1. l[i] = L（$i$ 的左邻居是 $L$）
2. r[i] = k（$i$ 的右邻居是 $k$）
3. 如果 $L \neq 0$，则 r[L] = i（$L$ 的右邻居改为 $i$）
4. l[k] = i（$k$ 的左邻居改为 $i$）

注意：如果 $k$ 本来就是队首（即 $L = 0$），那么插入后 $i$ 成为新的队首，此时不需要修改 r[0]，但需要记录新的队首编号。当然，我们也可以统一用 $0$ 作为哨兵节点来处理边界情况。

同理，$p=1$（插入到 $k$ 右边） 的指针变化为：

1. l[i] = k
2. r[i] = R（$R$ 是 $k$ 右边的同学）
3. r[k] = i
4. 如果 $R \neq 0$，则 l[R] = i

3.3 删除操作的实现

给定编号 $x$，如果 $x$ 已经不在队列中（vis[x] == false），则直接忽略。

否则，设 $x$ 的左邻居为 $L = l[x]$，右邻居为 $R = r[x]$。删除 $x$ 后，需要将 $L$ 和 $R$ 直接相连：

1. 如果 $L \neq 0$，则 r[L] = R
2. 如果 $R \neq 0$，则 l[R] = L
3. 标记 vis[x] = false

注意：如果 $x$ 是队首（$L = 0$），删除后 $R$ 成为新的队首；如果 $x$ 是队尾（$R = 0$），删除后 $L$ 成为新的队尾。这两种情况在上述逻辑中都能正确处理。

3.4 如何确定队首？

插入和删除操作都可能改变队首。我们可以在每次插入 $p=0$ 且 $k$ 是队首时更新队首为 $i$；在每次删除时，如果删除的是队首则更新队首为 r[x]。

但更简单的方式是：最后输出时从 $1$ 开始沿着 $r$ 指针找，直到找到某个节点其左邻居为 $0$，那就是队首。或者，我们在初始化时用变量 head 记录队首，每次操作后维护它。

推荐维护 head 变量，避免最后遍历查找。

3.5 关于重复删除指令

题目明确指出：如果 $x$ 号同学已经不在队列中则忽略这一条指令。因此每次删除前必须检查 vis[x]。

4. 完整代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int l[MAXN], r[MAXN];
bool vis[MAXN];  // true 表示仍在队列中

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    // 初始化：1号同学单独入队
    l[1] = r[1] = 0;
    vis[1] = true;
    int head = 1;  // 队首编号

    // 2 ~ N 号同学依次入列
    for (int i = 2; i <= N; i++) {
        int k, p;
        cin >> k >> p;
        vis[i] = true;

        if (p == 0) {
            // 插入到 k 的左边
            int L = l[k];
            l[i] = L;
            r[i] = k;
            if (L != 0) r[L] = i;
            l[k] = i;
            // 如果 k 原来是队首，则 i 成为新队首
            if (L == 0) head = i;
        } else {
            // 插入到 k 的右边
            int R = r[k];
            l[i] = k;
            r[i] = R;
            r[k] = i;
            if (R != 0) l[R] = i;
            // 如果 k 原来是队尾，则 i 成为新队尾（队首不变）
            // 队首不会因为插入到右边而改变
        }
    }

    int M;
    cin >> M;

    while (M--) {
        int x;
        cin >> x;
        if (!vis[x]) continue;  // 已经不在队列中，忽略

        int L = l[x], R = r[x];
        if (L != 0) r[L] = R;
        if (R != 0) l[R] = L;
        // 如果删除的是队首，更新队首
        if (x == head) head = R;
        vis[x] = false;
    }

    // 从队首开始遍历输出
    for (int cur = head; cur != 0; cur = r[cur]) {
        cout << cur << ' ';
    }
    cout << '\n';

    return 0;
}

5. 复杂度分析

• 时间复杂度：每个同学至多入队一次、出队一次，每次插入和删除操作均只修改常数条指针，故总时间复杂度为 $O(N + M)$。
• 空间复杂度：使用三个大小为 $N+1$ 的数组，$O(N)$。

6. 知识拓展：为什么不用 std::list？

C++ STL 中的 std::list 是双向链表，理论上也能完成本题。但需要注意：

• std::list 的迭代器在插入和删除后不会失效（除了被删除的迭代器），这本来是优点。
• 但本题要求按编号 $i$ 快速定位到节点。如果用 std::list，需要额外维护一个数组 pos[i] 存储编号为 $i$ 的同学对应的迭代器，代码复杂度反而更高。
• 数组模拟双向链表在算法竞赛中更常见：代码简洁、常数小、调试方便。

7. 常见错误与避坑指南

错误类型	错误写法	正确写法
插入时忘记处理边界	只修改 l[i]、r[i] 和 l[k]，忘记修改 L 的 r 指针	必须同时修改 L 的 r 和 k 的 l
删除时忘记更新队首	删除队首后 head 仍指向已删除节点	删除时判断 if (x == head) head = R
重复删除未检查	直接删除，导致指针错乱	每次删除前 if (!vis[x]) continue
插入顺序错误	先修改 l[k] 再获取 L	先获取 L 或 R 再修改，避免信息丢失

8. 总结

本题是双向链表的经典应用题，核心考察点在于：

1. 识别数据结构的适用场景——频繁的中间插入和删除 $\Rightarrow$ 链表。
2. 数组模拟链表的实现技巧——用编号直接索引前驱和后继，$O(1)$ 定位。
3. 边界条件的细致处理——队首、队尾、空队列等情况。

掌握了这些，遇到类似的“动态维护序列”问题（如插队、排队、LRU 缓存等）时，就能游刃有余了。