洛谷P1160——队列安排(双向链表)
2024-08-31 02:59:54
题目描述
一个学校里老师要将班上N个同学排成一列,同学被编号为1~N,他采取如下的方法:
1.先将1号同学安排进队列,这时队列中只有他一个人;
2.2~N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1~i -1中某位同学(即之前已经入列的同学)的左边或右边;
3.从队列中去掉M(M<N)个同学,其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
输入输出格式
输入格式:
输入的第1行为一个正整数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号同学已经不在队列中则忽略这一条指令。
输出格式:
输出仅包括1行,包含最多N个空格隔开的正整数,表示了队列从左到右所有同学的编号,行末换行且无空格。
输入输出样例
输入样例#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%的数据,有N≤10;
对于40%的数据,有N≤1000;
对于100%的数据,有N, M≤100000。
建立一个双向链表,链表中的每一个元素具有前驱和后继,插入元素的时候根据插入位置进行链表操作,插入的前继改变next域,后继改变pre,然后插入该元素,当前驱和后继的值都为-1的时候认为该元素被删除,把链表头节点0的next指向第一个节点,最后输出就行了。
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 struct node
5 {
6 int pre;
7 int next;
8 }queue[100050];
9 int main()
10 {
11 int n,m;
12 cin>>n;
13 queue[0].next=1;
14 queue[1].pre=0;
15 queue[1].next=-1;
16 for(int i=2;i<=n;i++)
17 {
18 int k,p;
19 cin>>k>>p;
20 if(p==1)//当插入k号同学的右边时
21 {
22 queue[i].pre=k;//第i号同学的前驱设为第k号同学
23 queue[queue[k].next].pre=i;//把第k号同学 原来的 后继同学的前驱 指向第i号同学
24 queue[i].next=queue[k].next;//把第i号同学的后继指向 第k号原来的同学
25 queue[k].next=i;//第k号同学的后继改为第i号
26 }
27 else//当插入k号同学的左边时
28 {
29 queue[i].next=k;//第i号同学的后继设为第k号同学
30 queue[queue[k].pre].next=i;//把第k号同学 原来的 前驱同学的后继 指向第i号同学
31 queue[i].pre=queue[k].pre;//把第i号同学的前驱指向 第k号原来的同学
32 queue[k].pre=i;//第k号同学的前驱改为第i号
33 }
34 }
35 cin>>m;
36 for(int i=1;i<=m;i++)
37 {
38 int temp;
39 cin>>temp;
40 if(queue[temp].pre==-1&&queue[temp].next==-1)
41 continue;//当前驱和后继都是负数时,认为该元素已经被删除
42 queue[queue[temp].pre].next=queue[temp].next;
43 queue[queue[temp].next].pre=queue[temp].pre;
44 queue[temp].next=-1;
45 queue[temp].pre=-1;//删除temp元素
46 }
47 int head=queue[0].next;
48 while(head!=-1)
49 {
50 cout<<head<<" ";
51 head=queue[head].next;//当输出最后一个链表元素时,其后继为-1,故跳出循环
52 }
53 return 0;
54 }
最新文章
- sublime text 插件
- RabbitMQ 入门 Helloworld
- 《Pro Express.js》学习笔记——概述
- linux基础3——与XP共享文件夹的设置
- MySQL 系列(五) 多实例、高可用生产环境实战
- chrome设置--disable-web-security解决跨域
- ZOJ 2677 Oil Deal(最大生成树)
- E8.Net工作流平台开发篇
- General: Know How to Use InetAddress
- Java导出Excel和CSV(简单Demo)
- 联系我们_你我想法_【有男度】UNANDU 100%进口 全球设计师品牌精汇 男装_男装搭配_时尚男装_品牌男装_男装搭配技巧_男装网站
- jQuery简介以及jQuery选择器
- Jquery网页选项卡应用
- 为什么要web语义化
- 面向对象的JS代码
- TypeScript入门知识二(参数新特性)
- Data_Struct(LinkList)
- Spring cloud整体框架
- NavUtils【底部虚拟导航栏工具类】
- 把list集合的内容写入到Xml中,通过XmlDocument方式写入Xml文件中