P1160 队列安排
队列安排
题目描述
一个学校里老师要将班上 N 个同学排成一列，同学被编号为 1~ N，他采取如下的方法：
-
先将 1 号同学安排进队列，这时队列中只有他一个人；
-
2~ N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1~(i-1) 中某位同学（即之前已经入列的同学）的左边或右边；
-
从队列中去掉 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
样例输入 #1
4
1 0
2 1
1 0
2
3
3
样例输出 #1
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% 的数据，1≤ N≤ 10。
对于 40% 的数据，1≤ N≤ 1000。
对于 100% 的数据，1<M≤ N≤ 10^5。
分析
若有错误，请谅解
这道题是一道典型的模拟题，故本蒟蒻第一个想到的就是用数组（太年轻），然后每加一个同学，就把他后面的同学位置整体向后挪，将他放进去，然后
就没有然后了···
对于N，M ≤ 100000和这个无比粗暴的方法，不TLE就是奇迹
妄想偷懒不行，只能好好分析一下题
稍加观察可以看出，这是一个链式结构，移动同学肯定是不行的（时间复杂度太高），那么，只能对他们间的关系下手了
我们可以把每相邻的的两个同学想象成他们牵着手（如图）
既然如此，我们就只需要改动左右手指向的同学就可以了 定义一个结构体
struct T{
int l,r; //每个同学的“左右手”
}t[mx]={0};
现在我们就手动模拟一下加入同学（以右边为例） 将编号为J的同学加入编号为i的同学右边
第一步 J的右手牵I右手牵的同学
t[j].r=t[i].r;
第二步 J的左手牵I
t[j].l=i;
第三步 I的右手牵J
t[i].r=j;
第四步 J右手牵的同学的左手牵J
注意：此时I的右手已经不牵原来那个同学了
t[t[j].r].l=j;
此时J就加入链当中了
左边同理
加入函数如下
void add(int i,int k,int f) //新增同学
{
if(f==1) //右
{
t[k].r=t[i].r;
t[k].l=i;
t[i].r=k;
t[t[k].r].l=k;
}
else //左
{
t[k].r=i;
t[k].l=t[i].l;
t[i].l=k;
t[t[k].l].r=k;
}
}
接下来是移除
我们虽然也可以用上面方法来删除
不过我用的是另一种方法（主要是懒）
我们可以给每个同学一个标记，标记了的将不会输出
struct T{
int l,r; //每个同学的“左右手”
int d; //表示同学是否输出
}t[mx]={0};
结构体
while(m--)
{
cin>>x; //要删去的同学
t[x].d=1; //将该同学标记为不输出
}
标记
接下来是细节问题
链的初始化
如果我们将1同学先输入进去
t[1].l=1,t[1].r=1;
因为没有其他同学只能自己牵自己（紧紧抱住弱小的自己）
但如果这样，到输出时就有一个问题（以样例为例）
找不到开头！
这时我们就要在初始化时动些手脚
t[0].r=0,t[0].l=0;
add(0,1,1);
定义个0同学 链将变成这样
我们只要从0的右手牵的同学开始输出，再到0结束就行了
输出代码
for (int i=t[0].r;i;i=t[i].r)
{
if (t[i].d==0) //输出未标记的
cout<<i<<" ";
}
提交答案
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int mx=1e5+10;
int n,m;
struct T{
int l,r; //每个同学的“左右手”
int d; //表示同学是否输出
}t[mx]={0};
void add(int i,int k,int f) //新增同学
{
if(f==1) //左
{
t[k].r=t[i].r;
t[k].l=i;
t[i].r=k;
t[t[k].r].l=k;
}
else //右
{
t[k].r=i;
t[k].l=t[i].l;
t[i].l=k;
t[t[k].l].r=k;
}
}
int main()
{
int x,k,f;
cin>>n;
t[0].r=0,t[0].l=0;
add(0,1,1);
for (int i=2;i<=n;i++)
{
cin>>x>>f;
add(x,i,f);
}
cin>>m;
while(m--)
{
cin>>x;
t[x].d=1; //将该同学标记为不输出
}
for (int i=t[0].r;i;i=t[i].r)
{
if (t[i].d==0) //输出未标记的
cout<<i<<" ";
}
return 0;
}