Luogu P1160队列安排【链表/老文搬家】By cellur925

原文发表于2018-04-15 08:15:09，我的luogu博客qwq。

看到题以后，要求维护一个可在任意位置修改添加删除元素的序列，那么显然我们可以用到链表。

然而本蒟蒻不久前刚刚学会链表。链表也是线性结构，和数组比较，它的物理内存不连续，逻辑内存连续。数组在任意位置插入删除元素效率极差，链表就很棒了。

下面是给和我一样蒟的老哥们。

链表通常用结构体存储，一个节点有三个值，前驱、后继、权值。

链表初始化

 int init()

 {

    tot=;

    head=;tail=;

    node[head].next=tail;

    node[tail].pre=head;

 }

在p后插入新节点注意是在后

 void insert(int p,int r)//插在p的后面

 {

     q=++tot;

     node[q].val=r;

     node[node[p].next].pre=q;

     node[q].next=node[p].next;

     node[p].next=q;

     node[q].pre=p;

 }

删除一节点

 void remove(int p)

 {

     node[node[p].pre].next=node[p].next;

     node[node[p].next].pre=node[p].pre;

 }

这些是链表的基本操作。

这道题需要有一些变动。

由于每个人按号依次进入，所以val值就是本身的序号。

由于可以向左插也可以向右插，写这句的时候要有一些改动。向右直接插，向左需要向向左插的节点的前驱插。

最后输出尤为注意。不能输出权值！具体见代码。

code

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,m,q,tmp,rp;

 int tot=;

 int head;

 bool b[];

 struct linkb{

     int val;

     int pre,next;

 }node[];

 void insert(int p,int r)//插在p的后面

 {

     q=++tot;

     node[q].val=r;

     node[node[p].next].pre=q;

     node[q].next=node[p].next;

     node[p].next=q;

     node[q].pre=p;

 }

 void remove(int p)

 {

     node[node[p].pre].next=node[p].next;

     node[node[p].next].pre=node[p].pre;

 }

 int main()

 {

     b[]=;node[].val=;

     node[].next=;

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         b[i]=;

         if(y==)

         {

             insert(x,i);

         }

         else if(y==)

         {

             insert(node[x].pre,i);

         }

     }

     scanf("%d",&m);

     for(int i=;i<=m;i++)

     {

         int x=;

         scanf("%d",&x);

         if(b[x]==) continue;

         b[x]=;

         rp++;

         remove(x);

     }

     head=node[].next;

     //printf("%d ",node[head].val);

     tmp=head;

     for(int i=;i<=n-rp;i++)

     {

         printf("%d ",node[tmp].val);

         tmp=node[tmp].next;

     }

     printf("\n");

     return ;

 }

巴特西

Luogu P1160队列安排【链表/老文搬家】By cellur925

最新文章

热门文章