双向链表练习题

[刷题记录]洛谷P1160 队列安排

• 年前刷的题，没来得及整理，年后来搞一下。

---

P1160 队列安排

• 题目链接

题意

老师要将$N$个同学排成一列，她首先把$1$号同学排进去，随后$2…N$号同学入队，由老师指定编号为$i$的同学站在编号为$1…(i-1)$的某位同学的左边或右边，除此之外，老师还可以从队列中去除M个同学，而其他的同学位置顺序不变。

最后要求你输出队列同学的编号。

Sample Input

4 //表示共有4个同学
1 0 //将2号同学插入到1号同学的左边
2 1 //将3号同学插入到2号同学的右边
1 0 //将4号同学插入到1号同学的左边
2 //表示有2个需要去除的同学
3 //去除3号同学
3 //去除3号同学（已去除，故无效）

Sample Output

2 4 1

思路&解法

• 看到需要插入和删除操作的序列，很明显是一道链表题，对于我这种刚学数据结构的蒟蒻来说，还是要慢慢搞的，附上代码（含注释）。

• 我使用的是比较容易的结构体数组定义方式，指针还不够熟练orz。

• 其中最关键的插入和删除操作，为方便理解，我画了个图，如下：

  add_left

  

  add_right

  

  erase

  

AC代码

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

struct node{ //定义链表中的每一个元素
	int L,R; //前驱与后继
}q[100005]; //结构体数组
int n;
void add_left(int pos, int x){ //在pos位置左边插入x元素
	q[x].R = pos; 
	q[x].L = q[pos].L;
	q[q[pos].L].R = x;
	q[pos].L = x;
}
void add_right(int pos, int x){ //在pos位置右边插入x元素
	q[x].L = pos;
	q[x].R = q[pos].R;
	q[q[pos].R].L=x;
	q[pos].R = x;
}
void erase(int x){ //删除x元素
	if(q[x].L==-1) return;
	q[q[x].L].R = q[x].R;
	q[q[x].R].L = q[x].L;
	q[x].L=-1;
	q[x].R=-1;
}
void init(){ //初始化，把1号放入链表第一位
	for(int i=1;i<=n;i++){
		q[i].L=q[i].R=-1;
	}
	q[0].R=1;
	q[1].L=0;
	q[1].R=-1;
}
int main(){
	cin>>n;
	init();
	for(int i=2;i<=n;i++){
		int x,y;
		cin>>x>>y;
		if(y==1) add_right(x,i);
		else add_left(x,i);
	}
	int m;
	cin>>m;
	while(m--){
		int x;
		cin>>x;
		erase(x);
	}
	int x = q[0].R;
	while(1){ // 遍历链表并输出
		cout<<x<<" ";
		if(q[x].R==-1) break;
		x=q[x].R;
	}
	return 0;
} 

---