洛谷 P1160：队列安排 ← 数组模拟

【题目来源】
https://www.luogu.com.cn/problem/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 个空格隔开的整数，表示了队列从左到右所有同学的编号。

【输入样例】
4
1 0
2 1
1 0
2
3
3

【输出样例】
2 4 1

【数据范围】
对于 20% 的数据，1≤N≤10。
对于 40% 的数据，1≤N≤1000。
对于 100% 的数据，1<M≤N≤10^5。

【算法分析】
● 本题利用数组模拟实现双链表的代码思想，与“AcWing 827：双链表”的思想基本一致。详见：https://blog.csdn.net/hnjzsyjyj/article/details/150845789

● 本题利用数组模拟实现双链表的示意图，附设了 idx=0 及 idx=1 两个结点。之后，插入结点 2（idx=2）的示意图如下所示。

● 特别要注意，本题在删除某个结点时，要进行特判，看看待删结点是否还存在。若不存在，忽略此删除操作。

● 本题用 STL list 实现的代码，详见：https://blog.csdn.net/hnjzsyjyj/article/details/151970421

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int le[maxn],ri[maxn],v[maxn],idx;
bool st[maxn];
int n,m,k,q,x;void init() {ri[0]=1,le[1]=0;idx=2;
}void insert(int p,int x) {v[idx]=x;le[idx]=p,ri[idx]=ri[p];le[ri[p]]=idx,ri[p]=idx++;
}void remove(int k) {ri[le[k]]=ri[k];le[ri[k]]=le[k];
}int main() {init();insert(0,1);cin>>n;for(int i=2; i<=n; i++) {cin>>k>>q;if(q) insert(k+1,i);else insert(le[k+1],i);}cin>>m;while(m--) {cin>>x;if(!st[x]) {remove(x+1);st[x]=true;}}for(int i=ri[0]; i!=1; i=ri[i]) {cout<<v[i]<<" ";}return 0;
}/*
in:
4
1 0
2 1
1 0
2
3
3out:
2 4 1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/150845789
https://blog.csdn.net/hnjzsyjyj/article/details/151970421
https://www.luogu.com.cn/problem/solution/P1160​​​​​​​
https://blog.csdn.net/lq1990717/article/details/127429719