题4 队列安排

题4 队列安排

【问题描述】
一个学校里老师要将班上N 个同学排成一列,同学被编号为1~N,他采取如下的方法:
1. 先将1 号同学安排进队列,这时队列中只有他一个人;
2. 2~N 号同学依次入列,编号为i 的同学入列方式为:老师指定编号为i 的同学站在
编号为1~i -1 中某位同学(即之前已经入列的同学)的左边或右边;
3. 从队列中去掉M(M<N)个同学,其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
【输入文件】
输入文件arrange.in 的第1 行为一个正整数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 号同学已经
不在队列中则忽略这一条指令。
【输出文件】
输入文件arrange.out 仅包括1 行,包含最多N 个空格隔开的正整数,表示了队列从左
到右所有同学的编号,行末换行且无空格。
【样例输入】
4
1 0
2 1
1 0
2
3
3
【样例输出】
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%的数据,有N≤10;对于40%的数据,有N≤1000;
对于100%的数据,有N, M≤100000。

信息

难度
10
分类
(无)
标签
递交数
2
已通过
0
通过率
0%
上传者