P1160 队列安排
2024-09-07 15:31:50
题目描述
一个学校里老师要将班上N个同学排成一列,同学被编号为1~N,他采取如下的方法:
1.先将1号同学安排进队列,这时队列中只有他一个人;
2.2~N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1~i -1中某位同学(即之前已经入列的同学)的左边或右边;
3.从队列中去掉M(M<N)个同学,其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
输入输出格式
输入格式:
输入文件arrange.in的第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号同学已经不在队列中则忽略这一条指令。
输出格式:
输入文件arrange.out仅包括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。
标签是队列但是正解是链表。。
思路比较清晰,就是个链表。
但是逻辑可能稍微有点复杂
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int read(int & n)
{
char c='-';int x=;
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')
{
x=x*+(c-);
c=getchar();
}
n=x;
}
const int MAXN=;
struct node
{
int pre,nxt,pos,flag;
}s[MAXN];
int n,m,where,how;
int main()
{
read(n);
for(int i=;i<=n;i++)
{
s[i].flag=;// 一开始肯定都会出现
s[i].pos=;
s[i].pre=;
s[i].nxt=;
}
s[].pos=;
for(int i=;i<=n;i++)
{
read(where);// 目标同学
read(how);
if(how==)// 左边
{
s[s[where].pre].nxt=i;
s[i].pre=s[where].pre;
s[where].pre=i;
s[i].nxt=where;
if(s[where].pos==)
{
s[where].pos=;
s[i].pos=;
}
}
else
{
s[s[where].nxt].pre=i;
s[i].nxt=s[where].nxt;
s[where].nxt=i;
s[i].pre=where; }
} read(m);
for(int i=;i<=m;i++)
{
read(where);
if(s[where].flag==)continue;
if(s[where].pos==)
s[s[where].nxt].pos=;
s[where].flag=;
s[s[where].pre].nxt=s[where].nxt;
s[s[where].nxt].pre=s[where].pre;
}
for(int i=;i<=n;i++)
{
if(s[i].pos==)
{
printf("%d ",i);
int p=s[i].nxt;
while(p!=)
{
printf("%d ",p);
p=s[p].nxt;
}
}
}
return ;
}
最新文章
- 用scikit-learn学习K-Means聚类
- Cenots7编译Opencv3.1错误:下载ippicv,解决方案
- Catia CAA 二次开发 ---- 开发准备(0)
- linux64需要增加的依赖库
- [原博客] POJ 1067 取石子游戏
- Android本地JUnit Text
- js文字向上滚动代码
- 更改AngularJS的语法解析符号
- ios save image to album
- php单例模式与工厂模式
- Redis的部署
- C/C++ 控制台字体的变颜变色
- spring boot mvc系列-静态资源配置与MappingHandler拦截器
- Java类、超类、包
- java 重新抛出异常
- linux通过rpm和yum安装包
- jQuery单选组美化特效
- 第一章:模型层model layer
- android OOM 内存溢出
- angular 动态组件类型
热门文章
- wget下载网络图片
- Nginx与HAProxy的区别
- node使用npm一句命令停止某个端口号 xl_close_port
- SVN 资源权限管理系统 SVNAdmin
- HDU 1051 Wooden Sticks 贪心题解
- CentOS command
- Linux Centos7 Apache 訪问 You don&;#39;t have permission to access / on this server.
- JAVA进阶-网络编程
- Thinking in Java---多线程仿真:银行出纳员仿真+饭店仿真+汽车装配工厂仿真
- Azure Pack演示样例缩放部署架构