【简单数据结构】链表--洛谷P1160
题目描述
一个学校里老师要将班上NN个同学排成一列,同学被编号为1\sim N1∼N,他采取如下的方法:
先将11号同学安排进队列,这时队列中只有他一个人;
2-N2−N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1\sim (i -1)1∼(i−1)中某位同学(即之前已经入列的同学)的左边或右边;
从队列中去掉M(M<N)M(M<N)个同学,其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
输入格式
第11行为一个正整数NN,表示了有NN个同学。
第2-N2−N行,第ii行包含两个整数k,pk,p,其中kk为小于ii的正整数,pp为00或者11。若pp为00,则表示将ii号同学插入到kk号同学的左边,pp为11则表示插入到右边。
第N+1N+1行为一个正整数MM,表示去掉的同学数目。
接下来MM行,每行一个正整数xx,表示将xx号同学从队列中移去,如果xx号同学已经不在队列中则忽略这一条指令。
输出格式
11行,包含最多NN个空格隔开的正整数,表示了队列从左到右所有同学的编号,行末换行且无空格。
输入输出样例
4
1 0
2 1
1 0
2
3
3
2 4 1
说明/提示
样例解释:
将同学22插入至同学11左边,此时队列为:
2 121
将同学33插入至同学22右边,此时队列为:
2 3 1231
将同学44插入至同学11左边,此时队列为:
2 3 4 12341
将同学33从队列中移出,此时队列为:
2 4 1241
同学33已经不在队列中,忽略最后一条指令
最终队列:
2 4 1241
数据范围
对于20\%20%的数据,有N≤10N≤10;
对于40\%40%的数据,有N≤1000N≤1000;
对于100\%100%的数据,有N, M≤100000N,M≤100000。
代码:
1 #include <cstdio>
2 #include <list>
3
4 using namespace std;
5 bool vis[100003];
6 list<int> stus;
7 list<int>::iterator pos[100003];
8
9 int main()
10 {
11 int n;
12 scanf("%d",&n);
13 stus.push_back(1);
14 pos[1] = stus.begin();
15 for (int i=2;i<=n;i++)
16 {
17 int k,p;
18 scanf("%d%d",&k,&p);
19 if (p == 0)
20 {
21 pos[i] = stus.insert(pos[k],i);
22 }
23 else {
24 list<int>::iterator it = pos[k];
25 ++it;
26 pos[i] = stus.insert(it,i);
27 }
28
29 }
30 int m = 0;
31 scanf("%d",&m);
32 for (int i=0;i<m;i++){
33 int x;
34 scanf("%d",&x);
35 if (!vis[x]){
36 stus.erase(pos[x]);
37 vis[x] = true;
38 }
39 }
40 for (list<int>::iterator i = stus.begin(); i != stus.end();i++)
41 {
42 printf("%d ",*i);
43 }
44 return 0;
45 }
几点说明,为了遍历列表方便,使用一个pos的迭代器数组来存放队列的迭代器;insert()函数的两个参数(迭代器和值),将值插入在迭代器的左边,并且返回一个迭代器指向此时i的位置;如果想要实现插入对应数值的右边,将迭代器加一再插入在它的左边;
vis[]数组储存队列i处是否有数值,这样可以快速遍历队列;最后,使用迭代器遍历队列的时候,不能时迭代器等于队列的最后,否则越界。
最新文章
- 关于i++,++i 的理解
- SQLServer并发问题,先SELECT后UPDATE,避免并发脏读情况解决
- bzoj2555: SubString
- 最简单的Web服务器
- 修改host
- [SQL]断开并更改数据库名
- Linux--------------更改yum
- ie11下,插入框架Html
- 关于if语句后面的花括号
- socketio 握手前中断报错
- Hadoop学习笔记(3)hadoop伪分布模式安装
- [More Effective C++]条款22有关返回值优化的验证结果
- Caused by: java.lang.ClassNotFoundException: org.dom4j.DocumentException
- jdb
- 微服务框架——SpringCloud(二)
- xml可视化编辑器
- Light OJ 1009
- JAVA基础知识总结:十九
- rsync实现文件同步
- yum命令简介