队列安排

GitHub跳转原题关系图返回列表

用数组模拟双向链表，O(1) 实现同学在指定位置左右插入和删除。

OJ: luogu

题目 ID: P1160

难度:普及

标签:链表模拟python

创建: 2026-07-07 00:00

更新: 2026-10-07 10:17

题意

$1$ 号同学先入队。 $2\sim N$ 号同学依次插入到某个已入队同学的左边或右边。随后有 $M$ 次删除（可能删除已删除的同学，需忽略）。最后输出从左到右的同学编号。

思路

$N \leqslant 10^5$ ， $M \leqslant N$ 。如果用数组或 vector 直接模拟，每插入/删除一次可能需要移动大量元素，最坏 $O(N^2)$ ，会超时。

先看一个正确但只适合小数据的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * date: 2026-07-07 00:00:00
 */
// brute.cpp：小数据暴力解，用 vector 模拟插入和删除。
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> q;         // 队列，存储从左到右的同学编号
    q.push_back(1);        // 1 号同学初始在最左侧

    // 处理插入
    for (int i = 2; i <= n; i++) {
        int k, p;
        cin >> k >> p;
        // 找到 k 号同学在队列中的位置
        auto it = find(q.begin(), q.end(), k);
        if (p == 0) {
            q.insert(it, i);  // 插到 k 左边
        } else {
            q.insert(it + 1, i); // 插到 k 右边
        }
    }

    int m;
    cin >> m;
    // 处理删除
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        auto it = find(q.begin(), q.end(), x);
        if (it != q.end()) {
            q.erase(it);
        }
    }

    // 输出最终队列
    for (int x : q) cout << x << ' ';
    cout << '\n';

    return 0;
}

暴力的瓶颈在于 find + insert/erase，每次操作的代价跟当前队列长度成正比。

其实，插入一个同学只影响他插入位置相邻的两个同学。双向链表恰好支持 $O(1)$ 的「在指定节点左侧/右侧插入」和「删除指定节点」。题目的操作完美对应：

插入到 k 左边：修改 L[k]、R[L[k]]、L[i]、R[i]
插入到 k 右边：修改 R[k]、L[R[k]]、L[i]、R[i]
删除 x：修改 R[L[x]] 和 L[R[x]]，将 x 标记为已删除

由于题目直接用编号引用同学，我们用数组 L[i] / R[i] 记录编号 i 的左、右邻居。数组下标即节点，不需要指针，适合竞赛写法和调试。

指针变化示意

这张表展示把新同学 i 插入到同学 k 左边时，数组双向链表需要改哪些指针：

步骤	操作	含义
1	`left_k = L[k]`	先记住 `k` 原来的左邻居
2	`L[i] = left_k`，`R[i] = k`	让 `i` 连接到 `left_k` 和 `k` 中间
3	`R[left_k] = i`（若存在）	原来的左邻居改为指向 `i`
4	`L[k] = i`	`k` 的左邻居改成 `i`

插入到右边是完全对称的：先记住 right_k = R[k]，再让 k <-> i <-> right_k 连起来。这里的核心是只修改相邻几个点，不移动整个序列。删除 x 也是同样思想，把 L[x] 和 R[x] 直接接起来即可。

删除时不是等到输出时跳过，而是直接把 x 从链表中摘除。del[x] 的作用是记录这个同学已经被删除过，避免第二次删除同一个编号时重复修改链表。

遍历输出时先找到链表头（没有左邻居且未被删除的节点），然后沿 R[] 向右输出。

Python 知识

left/right 两个列表按学生编号直接索引，作用与 C++ 数组相同，但无需预设固定最大值。
tokens=iter(map(int,sys.stdin.buffer.read().split())) 配合 next(tokens) 按题面顺序消费大量纯整数。
next((student for ...),0) 查找表头；若所有人都删除，默认返回 0。
列表 removed 保存布尔状态，重复删除时直接跳过。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：整数 token 迭代器输入。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：next(generator,default) 查找首个元素。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45import sys


tokens = iter(map(int, sys.stdin.buffer.read().split()))
n = next(tokens)
left = [0] * (n + 1)
right = [0] * (n + 1)
removed = [False] * (n + 1)

for student in range(2, n + 1):
    neighbor, side = next(tokens), next(tokens)
    if side == 0:
        previous = left[neighbor]
        left[student], right[student] = previous, neighbor
        left[neighbor] = student
        if previous:
            right[previous] = student
    else:
        following = right[neighbor]
        left[student], right[student] = neighbor, following
        right[neighbor] = student
        if following:
            left[following] = student

for _ in range(next(tokens)):
    student = next(tokens)
    if removed[student]:
        continue
    removed[student] = True
    previous, following = left[student], right[student]
    if previous:
        right[previous] = following
    if following:
        left[following] = previous

head = next(
    (student for student in range(1, n + 1) if not removed[student] and left[student] == 0),
    0,
)
answer = []
while head:
    answer.append(head)
    head = right[head]

print(*answer)

STL 写法

C++ 里可以直接用标准库的 list<int> 保存队伍：它是双向链表，每个同学单独占一个节点，节点之间靠链接相连。再开一个 list<int>::iterator pos[] 数组记住每个同学所在的节点，插入到 k 左边就是 insert(pos[k], i)，插入到右边先 ++it 再插入，删除用 erase(pos[x])——都是已知节点位置的 $O(1)$ 操作，正好对上本题「频繁在中间插人、删人」的需求。它和上面数组模拟双向链表的思路一样，只是把手工维护的 L[] / R[] 换成了库里的迭代器。

对应的 cppbook 章节：list：用节点连接起来的序列

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 00:52
 * update_at: 2026-10-07 00:53
 */
// main-stl.cpp：这是 STL 写法，用 list<int> 保存队伍，用 list<int>::iterator pos[] 记住每个同学在链表中的位置。
// 插入到 k 左边就把 pos[k] 交给 insert，插入到右边先 ++it；删除用 erase(pos[x])。
// 迭代器一直指向那个节点，插入/删除都不会让它失效，所以三种操作都是 O(1)，整体 O(N+M)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll n, m;
list<int> line;                 // line 保存队伍，从左到右就是链表从头到尾的顺序
list<int>::iterator pos[MAXN];  // pos[x] 是编号 x 的同学在链表中的位置（迭代器）
bool removed[MAXN];             // removed[x] = true 表示编号 x 已出队，重复指令要忽略

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

    cin >> n;

    // 1 号同学先入队，此时链表里只有他一个人
    line.push_back(1);
    pos[1] = line.begin();

    // 2~n 号同学依次插入到 k 号同学的左边或右边
    for (int i = 2; i <= n; i++) {
        int k, p;
        cin >> k >> p;

        if (p == 0) {
            // 插到 k 的左边：把 i 插在 pos[k] 这个位置之前，insert 返回新节点的迭代器
            pos[i] = line.insert(pos[k], i);
        } else {
            // 插到 k 的右边：先把游标后移一格到 k 的下一个节点，再在它之前插入 i
            list<int>::iterator it = pos[k];
            ++it;
            pos[i] = line.insert(it, i);
        }
    }

    // m 次删除，每次都是已知节点位置的 O(1) 删除
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        int x;
        cin >> x;
        if (removed[x]) {
            continue; // x 已经不在队列中，忽略这条指令
        }
        removed[x] = true;
        line.erase(pos[x]); // 删除 pos[x] 指向的节点，它的前后邻居自动接上
    }

    // 链表本身就是从左到右的顺序，用迭代器从头到尾输出
    for (list<int>::iterator it = line.begin(); it != line.end(); ++it) {
        cout << *it << ' ';
    }
    cout << '\n';

    return 0;
}

复杂度

时间复杂度： $O(N+M)$ ，每次插入和删除都是 $O(1)$
空间复杂度： $O(N)$

总结

当题目有以下特征时，考虑双向链表：

需要在序列的任意位置插入/删除元素
能通过编号/指针直接定位要操作的位置
不需要随机访问（按下标查找）

本题所有操作都是按编号进行的，排序后的顺序也不需要随机访问，因此双向链表是天然的最优解。

P1160 队列安排

题目描述

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

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

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

输入格式

第一行一个整数 $N$ ，表示了有 $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

输入 #1

text

输出 #1

text

12 4 1

说明/提示

【样例解释】

将同学 $2$ 插入至同学 $1$ 左边，此时队列为：

2 1

将同学 $3$ 插入至同学 $2$ 右边，此时队列为：

2 3 1

将同学 $4$ 插入至同学 $1$ 左边，此时队列为：

2 3 4 1

将同学 $3$ 从队列中移出，此时队列为：

2 4 1

同学 $3$ 已经不在队列中，忽略最后一条指令

最终队列：

2 4 1

【数据范围】

对于 $20\%$ 的数据， $1\leq N\leq 10$ 。

对于 $40\%$ 的数据， $1\leq N\leq 1000$ 。

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

队列安排

目录

题意

思路

指针变化示意

Python 知识

代码

STL 写法

复杂度

总结