链表板子之排队模拟实现

前言

自己参考洛谷深入浅出的题解手搓的一个双向链表的板子，更适合我自己的胃口，特此记录

P1160 队列安排

题目描述

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

  1. 先将 1 号同学安排进队列，这时队列中只有他一个人；

  2. 2 ~ N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1 ~ (i - 1) 中某位同学（即之前已经入列的同学）的左边或右边；

  3. 从队列中去掉 M 个同学，其他同学位置顺序不变。

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

输入格式

第一行一个整数 N ，表示了有 N 个同学。

第 2 ~ N 行，第 i 行包含两个整数 k,p，其中 k 为小于 i 的正整数，p 为 0 或者 1。若 p 为 0，则表示将 i 号同学插入到 k 号同学的左边，p 为 1 则表示插入到右边。

第 N+1 行为一个整数 M，表示去掉的同学数目。

接下来 M 行，每行一个正整数 x，表示将 x 号同学从队列中移去，如果 x 号同学已经不在队列中则忽略这一条指令。

输出格式

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

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

struct node {
	int pre, nxt, key;
	node(int _pre = 0, int _nxt = 0, int _key = 0) {
		pre = _pre, nxt = _nxt, key = _key;
	} // 结构体初始化
};

node s[100010]; // 变量池
int indexx[100010]; // 记录元素（学生编号）在变量池中的下标
int tot = 1; // 列表都从1开始

void ins_front(int x, int y) {
	int now = indexx[x]; // 查找索引
	s[++tot] = node(s[now].pre, now, y);
	indexx[y] = tot; // 记录索引
	s[s[now].pre].nxt = indexx[y];
	s[now].pre = indexx[y];
}

void ins_back(int x, int y) {
	int now = indexx[x]; // 查找索引
	s[++tot] = node(now, s[now].nxt, y);
	indexx[y] = tot; // 记录索引
	s[s[now].nxt].pre = indexx[y];
	s[now].nxt = indexx[y];
}

void del(int x) {
	int now = indexx[x]; // 查找索引
	s[s[now].pre].nxt = s[now].nxt;
	s[s[now].nxt].pre = s[now].pre;
	indexx[x] = 0; // 更新索引为0
}

int main() {
	LL n, m;
	// 列表都进行初始化
	s[0] = node(0, 1, 0);
	s[1] = node(0, 0, 1);
	indexx[1] = 1;
	
	cin >> n;
	for (int i = 2; i <= n; i++) {
		int k, p;
		cin >> k >> p;
		if (p == 0) {
			ins_front(k, i);
		}
		else if (p == 1) {
			ins_back(k, i);
		}
	}
	
	cin >> m;
	while (m--) {
		int x;
		cin >> x;
		if (indexx[x] == 0) continue;
		del(x);
	}
	
	int now = s[0].nxt;
	while (now) {
		cout << s[now].key << " ";
		now = s[now].nxt;
	}
	
	return 0;
}