题解 P1160 【队列安排】

wzxx · 2017-08-24 20:52:52 · 题解

萌新来发一篇数组模拟双向链表的题解~

代码似乎长了点？不过思路是很清晰的，具体看注释。

#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的链表题