题解 P1160 【队列安排】

萌新来发一篇数组模拟双向链表的题解~ 代码似乎长了点？不过思路是很清晰的，具体看注释。 ```cpp #include<iostream> #include<cstdio> using namespace std; int Node[100005],L[100005],R[100005];//Node存放学生的编号，L存放第i个人左边的人在哪里，R存放第i个人右边的人在哪里 int main() { int n=0,m=0; scanf("%d",&n);//读入 Node[1]=1;//第一个人先进去 for(int i=2;i<=n;i++) { int x=0,y=0; scanf("%d%d",&x,&y);//读入 Node[i]=i;//记录第i个人的编号 if(y==0)//如果是插入到左边 { R[i]=x;//第i个人右边那个人的位置自然是x if(L[x]>0)//如果第x个人不是最左边的话 { L[i]=L[x];//第i个人左边那个人的位置就是原先x左边那个人的位置 R[L[x]]=i;//原先x左边那个人的右边就是i } L[x]=i;//x的左边就是i } else//否则 { L[i]=x;//第i个人左边那个人的位置就是x if(R[x]>0)//如果第x个人不是最右边 { R[i]=R[x];//第i个人右边那个人的位置就是原先x右边那个人的位置 L[R[x]]=i;//原先x右边那个人的左边就是i } R[x]=i;//x的右边就是i }//P.S:这段else里的代码就是把上面的反转一下，左变右，右变左...... } scanf("%d",&m);//读入 for(int i=1;i<=m;i++) { int x=0; scanf("%d",&x); Node[x]=-1;//被去掉的人标记为-1 } for(int i=1;i<=n;i++) if(L[i]==0)//找到最左边的那个人 { int T=i; while(T>0)//开始遍历，输出 { if(Node[T]!=-1) printf("%d ",Node[T]);//如果没被去掉，就输出 T=R[T];//移到接下来的右边那个人 } } return 0; } 谨此纪念第一道AC的链表题 ```