P1160 队列安排

news/2024/7/14 18:25:09/文章来源:https://blog.csdn.net/2301_82112557/article/details/139275496

题目描述

一个学校里老师要将班上 N 个同学排成一列,同学被编号为 1∼N,他采取如下的方法:

  1. 先将 1 号同学安排进队列,这时队列中只有他一个人;

  2. 2∼N 号同学依次入列,编号为 i 的同学入列方式为:老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学(即之前已经入列的同学)的左边或右边;

  3. 从队列中去掉 M 个同学,其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数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 号同学已经不在队列中则忽略这一条指令。

输出格式

一行,包含最多 N 个空格隔开的整数,表示了队列从左到右所有同学的编号。

输入输出样例

输入 #1复制

4
1 0
2 1
1 0
2
3
3

输出 #1复制

2 4 1

思路:

1.考虑到这是一道模拟题,那我们需要模拟的部分就是

                                ↓

        如何放入一个插队者,并让他尽快融入队列

①考虑到可以创建一个add函数

    →执行将插队者插入右边,即p==1

    →执行将插入者插入左边,即p==0

2.整体函数内容出来后,我们考虑如何执行它

                               ↓

            考虑链表加结构体

②结构体的创建我就不详细说了

③那链表要如何使用?

   →当我们把队列想成一个人和人手拉手的圈,那么每个人就要有左右手,即l,r

   →当一个人被踢出圈中时,就要标记为不输出

struct node
{int l,r;        int d;        
};
node t[100005];

   →右:这个数的右手牵着原数右手边原来的数

              这个数的左手牵着原数

              原数的右手牵着这个数

              原数右手边原来的数的左手牵着这个数

if(p==1){t[i].r=t[k].r;t[i].l=k; t[k].r=i;t[t[i].r].l=i;
}

    →左:这个数的左手牵着原数左边原来的那个数

               这个数的右手牵着原数

               原数的左手牵着这个数

               原数左边原来的那个数的右手牵着这个数

else{t[i].l=t[k].l;t[i].r=k;t[k].l=i;t[t[i].l].r=i;
}

那么我们用什么方法确定是否输出呢

                        ↓

             及更改d的值

④遍历所有数,找到被踢出圈的人,不输出,即d标为1

cin>>m;
while(m--){cin>>x;t[x].d=1;        
}

⑤输出从左到右所有同学的编号

   →通过找右手牵着的人遍历

for(int i=t[0].r;i;i=t[i].r){if (t[i].d==0)   cout<<i<<" ";
}

代码:

 

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct node
{int l,r;int d;
};
node t[100005];
void add(int k,int i,int p)
{if(p==1){t[i].r=t[k].r;t[i].l=k;t[k].r=i;t[t[i].r].l=i;}else{t[i].l=t[k].l;t[i].r=k;t[k].l=i;t[t[i].l].r=i;}
}
int main()
{int x,k,p;cin>>n;t[0].r=0,t[0].l=0;add(0,1,1);for (int i=2;i<=n;i++){cin>>k>>p;add(k,i,p);}cin>>m;while(m--){cin>>x;t[x].d=1;}for(int i=t[0].r;i;i=t[i].r){if(t[i].d==0)cout<<i<<" ";}return 0;
}

 

 

 

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1053323.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringSecurity登录和校验流程简述

认证&#xff1a; 验证当前访问系统的是不是本系统的用户&#xff0c;并且要确认具体是哪个用户 授权&#xff1a; 经过认证后判断当前用户是否有权限进行某个操作 一、入门案例实现 搭建springboot工程后&#xff0c;创建启动类和Controller&#xff0c;引入SpringSecurity依…

基于高通公司AI Hub Models的On-Device AI学习:Introduction to On-Device AI

Introduction to On-Device AI 本文是学习 https://www.deeplearning.ai/short-courses/introduction-to-on-device-ai/这门课的学习笔记。 What you’ll learn in this course As AI moves beyond the cloud, on-device inference is rapidly expanding to smartphones, IoT…

详解Spring MVC

目录 1.什么是Spring Web MVC MVC定义 2.学习Spring MVC 建立连接 RequestMapping 注解介绍及使用 获取单个参数 获取多个参数 获取普通对象 获取JSON对象 获取基础URL参数 获取上传文件 获取Header 获取Cookie 获取Session 总结 1.什么是Spring Web MVC 官⽅对于…

基于.NetCore和ABP.VNext的项目实战二:Swagger

Mag.Blog.Swagger层添加Volo.Abp.AspNetCore和Swashbuckle.AspNetCore包,引用实体层.Domain 添加模块类MagBlogSwaggerModule.cs,依赖MagBlogDomainModule模块,并且重写ConfigureServices和OnApplicationInitialization方法 namespace Mag.Blog.Swagger {[DependsOn(typeof…

【教学类-58-06】黑白三角拼图06(1页3张彩色黑点卡片,一种宫格36张,适合一个班级一次操作)

作品展示 背景需求 【教学类-58-05】黑白三角拼图05&#xff08;2-10宫格&#xff0c;每个宫格随机1张-6张&#xff0c;带空格纸&#xff0c;1页3张黑白3张白卡&#xff09;-CSDN博客文章浏览阅读343次&#xff0c;点赞10次&#xff0c;收藏6次。【教学类-58-05】黑白三角拼图…

vue contextPath的思考

先说我这边的情况&#xff0c;目前项目都是前后端分离开发的&#xff0c;上线有种部署方式&#xff0c;常见的就是前后端分开部署&#xff0c;这是比较常见的&#xff0c;我这边因客户原因&#xff0c;打包一起进行部署比较简单&#xff0c;交付技术运维部方便后期其他现场部署…

5 分钟快速上手图形验证码,防止接口被恶意刷量!

5 分钟快速上手图形验证码&#xff0c;防止接口被恶意刷量&#xff01; 大家好&#xff0c;我是程序员小白条&#xff0c;今天来给大家介绍一个快速实现图形验证码的优秀框架 AJ-Captcha。 需求分析 如果注册接口没有验证码这种类型的限制&#xff0c;很容易会被刷量&#x…

python练习题-反转一个只有三位数的整数

【问题描述】&#xff1a;反转一个只有三位数的整数 [示例]&#xff1a;123 321 完整代码如下&#xff1a; nint(input()) if n<100 or n>999: print("请输入三位数&#xff01;") else: gen%10 shin//10%10 bain//100 m100*ge10*shibai…

电脑同时配置两个版本mysql数据库常见问题

1.配置时&#xff0c;要把bin中的mysql.exe和mysqld.exe 改个名字&#xff0c;不然两个版本会重复&#xff0c;当然&#xff0c;在初始化数据库的时候&#xff0c;如果时57版本的&#xff0c;就用mysql57(已经改名的)和mysqld57 代替 mysql 和 mysqld 例如 mysql -u root -p …

VLDB ’25 最后 6 天截稿,58 个顶会信息纵览;ISPRS 城市分割数据集上线

「顶会」板块上线 hyper.ai 官网啦&#xff01;该板块为大家提供最新最全的 CCF A 类计算机顶会信息&#xff0c;包含会议简介、截稿倒计时、投稿链接等。 你是不是已经注册了顶会&#xff0c;但对截稿时间较为模糊&#xff0c;老是在临近 ddl 时才匆忙提交&#xff1b;又或者…

Linux基础知识点总结!超详细

Linux 的学习对于一个IT工程师的重要性是不言而喻的&#xff0c;学好它是工程师必备修养之一。 Linux 基础 操作系统 操作系统Operating System简称OS&#xff0c;是软件的一部分&#xff0c;它是硬件基础上的第一层软件&#xff0c;是硬件和其它软件沟通的桥梁。 操作系统…

2024-05-28 服务器开发-不同vs版本的std::string的访问出错问题-记录

摘要: 有一个dll库是使用vs2010编译的, 使用这个dll动态库的工程是vs2019. 这个dll动态库返回一个结构体&#xff0c;其中有个成员使用了std::string。但是遇到了std::string的成员显示被赋值为NULL的情况。 本文对进行分析, 重点在于追踪问题的思路。 问题描述: dll使用vs20…

基于Pytorch框架的深度学习RegNet神经网络二十五种宝石识别分类系统源码

第一步&#xff1a;准备数据 25种宝石数据&#xff0c;总共800张&#xff1a; { "0": "Alexandrite","1": "Almandine","2": "Benitoite","3": "Beryl Golden","4": "Carne…

架构师系列---RPC通信原理

RPC通信原理 基于网络的调用 问题&#xff1a;谁来解决这个跨进程调用的问题&#xff1f; RPC&#xff1a;Remote Percedure Call 远程过程调用 定义了一台主机上的程序通过网络调用另外一台主机上的程序的子程序这一行为。 RPC符合CS模型&#xff0c;可以实现进程间的通信&a…

超详细的前后端实战项目(Spring系列加上vue3)前端篇(二)(一步步实现+源码)

好了&#xff0c;兄弟们&#xff0c;继昨天的项目之后&#xff0c;开始继续敲前端代码&#xff0c;完成前端部分 昨天完成了全局页面的代码&#xff0c;和登录页面的代码&#xff0c;不过昨天的代码还有一些需要补充的&#xff0c;这里添加一下 内容补充&#xff1a;在调用登…

vxe-form-design 表单设计器的使用

vxe-form-design 在 vue3 中表单设计器的使用 查看官网 https://vxeui.com 安装 npm install vxe-pc-ui // ... import VxeUI from vxe-pc-ui import vxe-pc-ui/lib/style.css // ...// ... createApp(App).use(VxeUI).mount(#app) // ...使用 github vxe-form-design 用…

Vue学习笔记2——创建一个Vue项目

Vue项目 1、创建一个Vue项目2、Vue项目的目录结构3、模版语法4、属性绑定5、条件渲染 1、创建一个Vue项目 vue官方文档&#xff1a; https://cn.vuejs.org/打开命令行界面&#xff08; “winR"再输入"cmd”&#xff09;&#xff0c;切换位置到指定的位置创建vue项目…

一文详解SpringBoot的自定义starter

目录 一、SpringBoot 二、自定义starter 三、SpringBoot的自定义starter 一、SpringBoot Spring Boot是一个开源的Java框架&#xff0c;由Pivotal团队&#xff08;现为VMware的一部分&#xff09;于2013年推出&#xff0c;旨在简化Spring应用程序的创建和部署过程。它基于S…

民国漫画杂志《时代漫画》第28期.PDF

时代漫画28.PDF: https://url03.ctfile.com/f/1779803-1248635321-5c67ad?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!

Linux一键安装Docker、kkfileviewer

Linux一键安装Docker、kkfileviewer 一、安装docker 安装docker脚本 vi initDocker.sh脚本内容 #安装前先更新yum&#xff0c;防止连接镜像失败 yum -y update#卸载系统之前的docker&#xff08;可选择&#xff0c;我这里直接注释了&#xff09; #yum remove docker docker…