题目链接
题目描述
一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $ 1 \sim N$，他采取如下的方法：
- 先将 $1$ 号同学安排进队列，这时队列中只有他一个人；
- $2 \sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim (i -1)$ 中某位同学（即之前已经入列的同学）的左边或右边；
- 从队列中去掉 $M(M<N)$ 个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
输入格式
第 $1$ 行为一个正整数 $N$ ，表示了有 $N$ 个同学。
第 $2 \sim N$ 行，第 $i$ 行包含两个整数 $k,p$，其中 $k$ 为小于 $i$ 的正整数，$p$ 为 $0$ 或者 $1$。若 $p$ 为00，则表示将 $i$ 号同学插入到 $k$ 号同学的左边，$p$ 为 $1$ 则表示插入到右边。
第 $N+1$ 行为一个正整数 $M$，表示去掉的同学数目。
接下来 $M$ 行，每行一个正整数 $x$，表示将 $x$ 号同学从队列中移去，如果 $x$ 号同学已经不在队列中则忽略这一条指令。
输出格式
$1$ 行，包含最多 $N$ 个空格隔开的正整数，表示了队列从左到右所有同学的编号，行末换行且无空格。
题解
使用双向链表模拟即可，注意不要写 ub
代码
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
| #include <iostream>
using namespace std;
struct d {
int l, r;
} a[100010];
int v[100010];
int n, m;
int k, p;
int main() {
cin >> n;
a[1].l = 0, a[1].r = 100009, a[0].r = 1;
for (int i = 2; i <= n; i++) {
cin >> k >> p;
if (p == 0)
a[i].l = a[k].l, a[i].r = k, a[a[k].l].r = i, a[k].l = i;
else
a[i].r = a[k].r, a[i].l = k, a[a[k].r].l = i, a[k].r = i;
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> k;
if (!v[k])
a[a[k].l].r = a[k].r, a[a[k].r].l = a[k].l, v[k] = true;
}
int bib = 0;
for (int i = 1; i <= n; i++) {
bib = a[bib].r;
if (bib != 100009)
cout << bib << " ";
else
break;
}
return 0;
}
|
注意
- 定义链表不存在中的元素时注意数组是否会越界
