【GESP】C++五级练习题 luogu-P1160 队列安排
GESP C++ 五级练习题，链表数据结构考点应用，五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
luogu-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
1
2
3
4
5
6
7
4
1 0
2 1
1 0
2
3
3
输出 #1
1
2 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$。
题目分析
本题主要考察 链表 的操作。
由于题目中涉及到频繁的插入和删除操作：
- 插入：需要将一个同学插入到另一个同学的左边或右边。
- 删除：需要将一个同学从队列中移出。
如果使用数组（Array）或 std::vector 进行模拟，每次在数组中间插入或删除元素都需要搬移后续所有元素，时间复杂度为 $O(N)$。在 $N=10^5$ 的情况下，总的时间复杂度可能达到 $O(N^2)$，这会导致超时。
因此，最合适的数据结构是 双向链表。链表可以在 $O(1)$ 的时间内完成节点的插入和删除。
- 每个节点记录其左边节点（
l）和右边节点（r）的编号。 - 插入时，只需要修改相关节点的指针（
l和r数组的值）。 - 删除时，只需将其左邻居指向其右邻居，其右邻居指向其左邻居即可。
具体实现细节：
- 使用数组模拟链表：利用
l[i]和r[i]两个数组分别存储同学 $i$ 左边和右边的同学编号。这种静态链表的方式编写简单，效率高。 - 边界处理：使用
0表示没有邻居（即队头或队尾）。 - 重复删除处理：题目可能会要求删除已经不在队列中的同学，代码中使用
deleted数组记录状态，避免重复操作。 - 队头维护：由于队头前面的元素可能会被插入新元素（变成新队头），或者队头元素被删除，因此需要维护一个
head变量指向当前的队头，以便最后遍历输出。
结构体实现方案
除了使用独立的数组 l 和 r，还可以使用结构体 struct 来封装每个节点的属性（左指针、右指针、删除标记）。这种方式代码逻辑封装性更好，更符合面向对象的思维，但在本题这种简单的链表操作中，效率和数组模拟基本一致。
示例代码
数组实现方案
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
int l[100005];
int r[100005];
bool deleted[100005];
int main() {
int N;
std::cin >> N;
l[1] = 0;
r[1] = 0;
int head = 1;
for (int i = 2; i <= N; i++) {
int k, p;
std::cin >> k >> p;
if (p == 0) {
// 将 i 插入到 k 的左边
if (l[k] == 0) {
head = i; // 如果 k 原来是头，即 l[k] == 0，既然 i 到了 k
// 左边，i 变成新头
}
// 链接 i 和 k 的左邻居（如果存在）
if (l[k] != 0) {
r[l[k]] = i; // k 的左邻居的右边现在是 i
}
l[i] = l[k]; // i 的左边是 k 原来的左边
// 链接 i 和 k
l[k] = i; // k 的左边现在是 i
r[i] = k; // i 的右边现在是 k
} else {
// 将 i 插入到 k 的右边
if (r[k] != 0) {
l[r[k]] = i; // k 的右邻居的左边现在是 i
}
r[i] = r[k]; // i 的右边是 k 原来的右边
// 链接 k 和 i
l[i] = k; // i 的左边是 k
r[k] = i; // k 的右边是 i
}
}
int M;
std::cin >> M;
// 使用 deleted 数组标记是否已删除，避免重复处理
while (M--) {
int x;
std::cin >> x;
if (deleted[x]) {
continue; // 如果 x 已经不在队列中，忽略
}
deleted[x] = true;
// 处理头节点情况
if (head == x) {
head = r[x]; // 头节点后移
}
// 1. 如果 x 有左邻居，让左邻居的右指针指向 x 的右邻居
if (l[x] != 0) {
r[l[x]] = r[x];
}
// 2. 如果 x 有右邻居，让右邻居的左指针指向 x 的左邻居
if (r[x] != 0) {
l[r[x]] = l[x];
}
// 清空 x 的指针（可选，但为了调试清晰保留）
l[x] = 0;
r[x] = 0;
}
// 输出队列
int curr = head;
while (curr != 0) {
std::cout << curr << ' ';
curr = r[curr];
}
return 0;
}
结构体实现代码
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
// 使用结构体定义节点
struct Node {
int l, r; // 左、右邻居的编号
bool deleted; // 删除标记
} nodes[100005];
int main() {
int N;
std::cin >> N;
// 初始化 1 号节点
nodes[1].l = 0;
nodes[1].r = 0;
nodes[1].deleted = false;
int head = 1; // 维护队头
for (int i = 2; i <= N; i++) {
int k, p;
std::cin >> k >> p;
nodes[i].deleted = false;
if (p == 0) {
// 将 i 插入到 k 的左边
// 1. 设置 i 的左右指针
nodes[i].l = nodes[k].l;
nodes[i].r = k;
// 2. 更新 k 左邻居的右指针 (如果存在)
if (nodes[k].l != 0) {
nodes[nodes[k].l].r = i;
} else {
// k 原本是队头，现在 i 插在 k 左边，i 变成新队头
head = i;
}
// 3. 更新 k 的左指针
nodes[k].l = i;
} else {
// 将 i 插入到 k 的右边
// 1. 设置 i 的左右指针
nodes[i].l = k;
nodes[i].r = nodes[k].r;
// 2. 更新 k 右邻居的左指针 (如果存在)
if (nodes[k].r != 0) {
nodes[nodes[k].r].l = i;
}
// 3. 更新 k 的右指针
nodes[k].r = i;
}
}
int M;
std::cin >> M;
while (M--) {
int x;
std::cin >> x;
if (nodes[x].deleted) {
continue;
}
nodes[x].deleted = true;
// 如果删除的是头节点，更新头节点
if (head == x) {
head = nodes[x].r;
}
// 链接 x 的左邻居和右邻居
if (nodes[x].l != 0) {
nodes[nodes[x].l].r = nodes[x].r;
}
if (nodes[x].r != 0) {
nodes[nodes[x].r].l = nodes[x].l;
}
}
// 从头遍历输出
int curr = head;
while (curr != 0) {
std::cout << curr << " ";
curr = nodes[curr].r;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
