PTA L2-014列车调度

PTAL2-014列车调度(二分法/Set集合)

两种方法解决该问题

火车站的列车调度铁轨的结构如下图所示。
在这里插入图片描述
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
输入格式
输入第一行给出一个整数N (2 ≤ N 1 0 5 10^5 105 ),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例

9
8 4 2 5 3 9 1 6 7

输出样例

4

思路剖析1

  • 采用set,set可以将元素按照从小到大排序,并且set可以找到比某一个元素大的第一个元素的位置迭代器,取引号就是它的值。
  • 这题就是将输入的那一串数放入轨道内,若出现要放的火车的序号大于该轨道的末尾火车序号,则需要重开轨道。
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int railWay[100010];
set<int> s;
int main()
{int N;cin >> N;int count = 0;int i;for (i = 1; i <= N; i++){cin >> railWay[i];}s.insert(0);// 刚开始已经有个铁轨了for (i = 1; i <= N; i++){if ((*s.rbegin()) < railWay[i]){count += 1;// s.insert(railWay[i]);s.insert(railWay[i]);// cout << "另起炉灶count:" << count << ", pos:" << railWay[i] << endl;continue;}else{s.erase(*(s.upper_bound(railWay[i])));s.insert(railWay[i]);}}cout << count << endl;return 0;
}

思路剖析2

  • 其实这题直接用数组存储每个轨道的队尾火车序号即可,不能插入就开轨道,能插入采用二分法找到大于且最接近目前要插入火车的序号的那个轨道,然后插入进去将该轨道的队尾火车序号变为当前的火车序号。
  • 有一个点要注意,就是你在执行上述的过程时,存放每一个轨道队尾序号的数组是规律递增的。认真想想,插不进去了是因为这个序号比所有目前的队尾序号都大,然后二分法找第一个比他的轨道,插入进去,此时刚插入的序号比之前的所有轨道的队尾序号都大!
// 太美妙了这个想法,竟然可以做到每一个铁轨的火车最小序号是递增的。
// 简述一下原理,首先每次往某一个铁轨上加火车,序号肯定是越来越小的(能加的情况),
// 若不能加,另开一个道,那么这个新的道肯定比原来那个道序号大,如果出现的能加的情况,那么肯定要找这个比当前这个火车的序号大的轨道,且是最接近的。
// 这样就又保证了插进去后,该轨道的最小序号肯定比他之前的轨道最小序列大!!!(序号不重复)
// 采用二分法找最接近的,因为每次找最接近且比他大的,最后l肯定会等于r,且在最接近且比他大的位置。#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int railWay[100010];
int minNum[100010];
set<int> s;
int main()
{int N;cin >> N;int i, j;int count = 1;int flag = 0;// int pos = 1;for (i = 1; i <= N; i++){cin >> railWay[i];}int maxRail = railWay[1];minNum[1] = maxRail;// s.insert(maxRail);int left = 0, right = 0, mid;// 刚开始已经有个铁轨了for (i = 2; i <= N; i++){flag = 0;if (minNum[count] < railWay[i]){count += 1;// s.insert(railWay[i]);minNum[count] = railWay[i];maxRail = railWay[i];// cout << "另起炉灶count:" << count << ", pos:" << railWay[i] << endl;continue;}left = 1, right = count;while(left<=right){mid = (left + right) / 2;if(minNum[mid]>railWay[i]){right = mid - 1;}else{left = mid + 1;}}minNum[left] = railWay[i];}cout << count << endl;return 0;
}

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

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

相关文章

UVA514 铁轨问题

问题描述 &#xff1a; PopPush城市有一座著名的火车站。这个国家到处都是丘陵。而这个火车站是建于上一个世纪。不幸的是&#xff0c;那时的资金有限。所以只能建立起一条路面铁轨。而且&#xff0c;这导致这个火车站在同一个时刻只能一个轨道投入使用&#xff0c;因为它缺少…

城市轨道交通的GoA

导言 目前轨道系统中最常见的便是基于通信的列车控制系统&#xff08;Communication Based Train Control, CBTC)&#xff0c;其中各集成商各条线路采用了不同级别的自动化技术&#xff0c;本文将针对CBTC的运用&#xff0c;从其系统组成、系统升级改造、系统主要功能、自动化…

铁路轨道不平顺数据分析与预测

铁路轨道不平顺数据分析与预测 1.引言 铁路轨道作为铁行车的基础设施&#xff0c;是铁路线路的重要组成部分。随着经济和交通运输业的发展&#xff0c;我国的铁路运输正朝着高速和重载方向迅速发展&#xff0c;与此同时&#xff0c;轨道结构承受来自列车荷载、运行速度的冲击…

铁轨问题 栈的运用

是这几天学习紫书遇到的一个问题 之前在学校的时候尝试着做过 题目如下 自己大概知道是这么个意思 C就相当于一个栈 进去的车厢只能倒着出来 后进去的就先出来 代码里不精 还是照着书上的打了一遍 花了一个下午理解了 #include<cstdio> #include<stack> usin…

栈的应用:火车调度问题

栈的应用&#xff1a;火车调度 问题概述 输入第一行是一个整数N&#xff0c;表示车厢的数量&#xff1b;第二行是一个由Y于R组成的字符串&#xff0c;表示车厢的排列&#xff0c;其中Y表示硬座&#xff0c;R表示软座。我们的任务&#xff0c;是借助一个栈&#xff0c;使得车厢…

火车进站问题-HDUOJ

火车进站问题 问题描述 假设杭州东火车站只有一条铁路&#xff0c;并且所有火车都从一侧进来&#xff0c;从另一侧出去。那么&#xff0c;如果火车A先进站&#xff0c;然后火车B在火车A离开之前就进站&#xff0c;那么火车A直到火车B离开后才能离开&#xff0c;可参见下图。 现…

深圳大学第三期“飞鹰计划”正式开班|学以致用,扬帆起航!

金秋九月&#xff0c;丹桂飘香&#xff0c;在这个充满着收获的季节里&#xff0c;迎来了期待已久的深圳大学机电与控制工程学院飞鹰计划2022级第三期开班典礼。受疫情影响&#xff0c;虽然典礼只能在线上举行&#xff0c;但是丝毫不影响电巢专家及学生们的热情。9月17日下午&am…

写了10 年的代码,收藏了这 20 个代码生成框架!

点击上方“Java基基”&#xff0c;选择“设为星标” 做积极的人&#xff0c;而不是积极废人&#xff01; 源码精品专栏 原创 | Java 2020 超神之路&#xff0c;很肝~中文详细注释的开源项目RPC 框架 Dubbo 源码解析网络应用框架 Netty 源码解析消息中间件 RocketMQ 源码解析数…

matlab偏最小二乘截距,matlab代写偏最小二乘回归(PLSR)和主成分回归(PCR)

原标题&#xff1a;matlab代写偏最小二乘回归(PLSR)和主成分回归(PCR) 原文&#xff1a;http://tecdat.cn/?p2655 此示例显示如何在matlab中应用偏最小二乘回归(PLSR)和主成分回归(PCR)&#xff0c;并讨论这两种方法的有效性。当存在大量预测变量时&#xff0c;PLSR和PCR都是对…

水上飞鹰(Z缓存alpha混合)

程序的描述:水上飞鹰(Z缓存alpha混合) 作者:lun 创建日期:2005-10-5 版本:0.1 编译环境:WIN2000 VC6 SP6 DXSDK 驾驶你水上飞艇! 穿越重重危险! 程序下载地址 http://www.wungaonline.com/read.php?tid-100.html

从中关村到纳斯达克,龚宇的奇异8年与爱奇艺的全新时代

十余载岁月风云&#xff0c;视频江湖风起云涌&#xff0c;大浪淘沙后爱奇艺、腾讯视频、优酷土豆三足鼎立之势已成。 北京时间 3 月 29 日晚间&#xff0c;爱奇艺在美国纳斯达克市场敲钟上市&#xff0c;证券代码为IQ&#xff0c;IPO 定价每股 18 美元&#xff0c;照此计算&am…

linux写c语言工具,Linux下用C语言实现推箱子游戏

前面有Linux的常用命令和vim文本编辑器还没有介绍&#xff0c;之后我会补上的。 今天来介绍如何用C语言写一个简单的小游戏&#xff0c;叫做“小老鼠推箱子”。虽然游戏的编写过程不复杂&#xff0c;但是我觉得能够从中找到自己对于编程的不足和完善自己的编程思维是最重要的。…

错别字检测的软件有哪些?自动检查错别字的工具 文字校对 文本纠错 查错别字 校对软件 错别字检查 论文格式 在线校对

我们日常生活中&#xff0c;无论从事什么行业做什么工作&#xff0c;都一定会需要在电脑上打字、写文章文件&#xff0c;而大部分人都难免出现写错别字的情况。这时候就很需要自动检查错别字的软件&#xff0c;来帮助我们快速解决错别字的问题。 爱校对 错别字在线识别检测 错…

如何写好需求文档?

有一天&#xff0c;一位朋友打电话给我。 朋友&#xff1a;“听说你们公司是做产权的&#xff0c;我这有相关的项目&#xff0c;你们能做吗&#xff1f;” 老吴&#xff1a;“我们公司现在不打算接项目了&#xff0c;以做产品为主。” 朋友&#xff1a;“你在公司负责什么啊…

以梦为马,不负韶华|电巢科技延安大学飞鹰计划实习班精彩回顾

时光流淌无声&#xff0c;昨天仿佛还初次见面&#xff0c;今天却又是一年的尾声。你是否结交到亲密的小伙伴&#xff1f;你是否感受到团队合作的魅力&#xff1f;你是否在延大这片沃土得到成长&#xff1f;假如你还没答案&#xff0c;那么看看其他人的回答。 在延安大学&#x…

oracle _读取,oracle中如何读写bold类型的数据

Oracle的Blob字段比较特殊,他比long字段的性能要好很多,可以用来保存例如图片之类的二进制数据。 写入Blob字段和写入其它类型字段的方式非常不同,因为Blob自身有一个cursor,你必须使用cursor对 blob进行操作,因而你在写入Blob之前,必须获得cursor才能进行写入,那么如何…

linux下mysql 大小写敏感 设置

说明&#xff1a; MySQL在Linux下数据库名、表名、列名、别名大小写规则是这样的&#xff1a;    1、数据库名与表名是严格区分大小写的&#xff1b;    2、表的别名是严格区分大小写的&#xff1b;    3、列名与列的别名在所有的情况下均是忽略大小写的&#xff1b;…

如何用python读写excel文件_如何用Python读写Excel文件?最便捷的3种方式

python读写excel的方式有很多&#xff0c;这里我介绍3种方式&#xff0c;一种是利用xlrd和xlwt进行excel读写&#xff0c;一种是openpyxl读写&#xff0c;最后一种是利用pandas进行读写&#xff0c;下面我主要介绍一下3种方式读写的过程&#xff0c;实验环境win7python3.6pycha…

基于模型的软件开发方法综述

文章目录 前言1 基于模型的软件开发概述2模型驱动架构2.1 模型驱动的软件体系结构2.2 模型驱动的软件开发步骤 3 建模语言3.1UML3.2 SysML3.3 AADL 4 软件建模工具4.1 Rhapsody4.2 SCADE4.3 Matlab4.3.1 Matlab Coder4.3.2 Simulink Coder 4.4 其他工具4.4.1 Enterprise Archit…

(附源码)spring boot流浪动物救助系统 毕业设计180920

目 录 摘要 1 1 绪论 1 1.1 研究背景 1 1.2国内外研究现状 1 1.3论文结构与章节安排 1 2 流浪动物救助系统系统分析 3 2.1 可行性分析 3 2.2 系统流程分析 3 2.2.1 数据流程 3 3.3.2 业务流程 4 2.3 系统功能分析 4 2.3.1 功能性分析 4 2.3.2 非功能性分析 5 2.4 系统用例分析 …