csu 1982: 小M的移动硬盘

1982: 小M的移动硬盘

Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 48 Solved: 10

Description

最近小M买了一个移动硬盘来储存自己电脑里不常用的文件。但是他把这些文件一股脑丢进移动硬盘后，觉得这些文件似乎没有被很好地归类，这样以后找起来岂不是会非常麻烦？
小M最终决定要把这些文件好好归类，把同一类地移动到一起。所以现在小M有了这几种操作：
1 u 表示把编号为u的文件放到最上面
2 u 表示把编号为u的文件放到最下面
3 u v 表示把编号为u的文件放到编号为v的文件的后面
已知在最开始的时候，1号文件到n号文件从上往下排布
现在小M已经给出了他所进行的所有操作，你能告诉他操作之后的序列是会变成什么样子吗？

Input

第一行为一个数字T（T<=10）表示数据组数
第二行为两个数字n、m（1<=n,m<=300000）表示序列长度和小M的操作次数
接下来m行每行两个或三个数字，具体含义见题面
保证数据合法

Output

输出一行表示小M操作结束后的序列

Sample Input

Sample Output

5 2 7 8 4 9 10 3 1 6

Hint

Source

2017年暑期集训校队选拔

Author

卢铭威

题解：

使用链表来模拟看一下数据大小还有时间的大小

可以知道只有使用链表才可以过

但是链表的查找时间是O（n）

所以我们要多设置多个指针 a[i]->next 指向i所在的那个位置

这样查找的时间就成了O（n）

  1 #include <cstdio>
  2 #include <time.h>
  3 #include <stdlib.h>
  4 #include <cstring>
  5 using namespace std;
  6 struct doublenode
  7 {
  8     int data;
  9     struct doublenode *next ,*prior ;
 10 };                      //定义一个双向链表
 11 typedef struct doublenode dnode; //格式化定义
 12 
 13 int main()
 14 {
 15     int t;
 16     scanf("%d",&t);
 17     while(t--)
 18     {
 19         int n,m;
 20         scanf("%d%d",&n,&m);
 21         dnode *pnew,*phead,*ptail,*pend,*pk_1,*pk,*pk1,*p1,*p2, *mp[300009];
 22         phead=(dnode *)malloc(sizeof(dnode));  //为链表设计一个头结点
 23         mp[0]=(dnode *)malloc(sizeof(dnode));
 24         phead->data=0;
 25         phead->next =NULL;
 26         phead->prior =NULL;
 27         ptail=phead;
 28         mp[0]->next=phead;
 29         mp[0]->prior=NULL;
 30         mp[0]->data=0;
 31         for(int i=1; i<=n; i++)
 32         {
 33             pnew=(dnode *)malloc(sizeof(dnode));  //生成头结点，尾插法
 34             pnew->data=i;
 35             ptail->next =pnew ;
 36             pnew->prior =ptail;
 37             ptail=pnew;
 38             ptail->next =NULL;
 39             mp[i]=(dnode *)malloc(sizeof(dnode));
 40             mp[i]->next=ptail;
 41             mp[i]->prior=NULL;
 42             mp[i]->data=i;
 43         }
 44         pend=(dnode *)malloc(sizeof(dnode));
 45 
 46         pend->prior=ptail;
 47         ptail->next=pend;
 48         pend->next=NULL;
 49         int haha=0;
 50         while(m--)
 51         {
 52 
 53             int c,k,d;
 54             scanf("%d",&c);
 55             if(c==1)
 56             {
 57                 scanf("%d",&k);
 58                 pk=mp[k]->next;
 59                 pk_1=pk->prior;
 60                 pk1=pk->next;
 61                 pk_1->next=pk_1->next->next;
 62                 pk1->prior=pk1->prior->prior;
 63                 p1=phead->next;
 64                 pk->next=p1;
 65                 pk->prior=phead;
 66                 phead->next=pk;
 67                 p1->prior=pk;
 68             }
 69             else if(c==2)
 70             {
 71                 scanf("%d",&k);
 72                 pk=mp[k]->next;
 73                 pk_1=pk->prior;
 74                 pk1=pk->next;
 75                 pk_1->next=pk_1->next->next;
 76                 pk1->prior=pk1->prior->prior;
 77 
 78                 p1=pend->prior;
 79                 pk->next=pend;
 80                 pk->prior=p1;
 81                 p1->next=pk;
 82                 pend->prior=pk;
 83             }
 84             else
 85             {
 86                 scanf("%d%d",&k,&d);
 87 
 88                 pk=mp[k]->next;
 89                 pk_1=pk->prior;
 90                 pk1=pk->next;
 91                 pk_1->next=pk_1->next->next;
 92                 pk1->prior=pk1->prior->prior;
 93 
 94                 p1=mp[d]->next;
 95                 p2=p1->next;
 96                 pk->next=p2;
 97                 pk->prior=p1;
 98                 p1->next=pk;
 99                 p2->prior=pk;
100             }
101             //printf("第%d步已经完成
",++haha);
102         }
103       //  printf("操作已完成
");
104       //  scanf("%d",&m);
105         pnew=phead->next;
106         while(pnew->next)
107         {
108             printf("%d ",pnew->data);
109             pnew=pnew->next;
110         }
111         printf("
");
112     }
113     return 0;
114 }