列车调度 思路解析

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

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

火车站的列车调度铁轨的结构如下图所示。

列车调度 思路解析

两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?

输入格式:

输入第一行给出一个整数N (2 ≤ N ≤10​5​​),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式:

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例:

9
8 4 2 5 3 9 1 6 7

输出样例:

4

解析:
    先将输入的第一个序号放到set中
    注意set中保存的是每个铁轨中序号最小的列车号 
    这样的意义在于,如果接下来输入的列车序号有比它还小的,那么他们就可以在同一铁轨中排着队
    对应的操作是:更新 对应铁轨中最小的列车序号
    接着输入数据,如果在set中找不到比输入列车序号小的,那就要新建铁轨,即向set中添加一个新的记录 
    最后,set中数据的个数,对应着所需铁轨的条数 


编译器 C++ (g++)

#include<stdio.h>
#include<set>
using namespace std;
int main()
{
	int n,num;
	scanf("%d %d",&n,&num);
	set<int> s;
	s.insert(num);
	for(int i=1;i<n;i++) 
	{
		scanf("%d",&num);
		if(s.lower_bound(num)!=s.end()){
			s.erase(s.lower_bound(num));
		}
		s.insert(num);
	}
	printf("%d",s.size());
	return 0; 
} 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/159406.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • MD5 编码 转换

    MD5 编码 转换

    2021年5月9日
    218
  • CCD传感器成像、尺寸、曝光时间「建议收藏」

    CCD传感器成像、尺寸、曝光时间「建议收藏」参考博主@机器视觉001的博文https://blog.csdn.net/liubing8609/article/details/78254703工业相机,最本质的功能就是将光信号转变成有序的电信号。CCD传感器成像过程1.用相机拍摄景物时,景物反射的光线通过相机的镜头透射到CCD上。2.当CCD曝光后,光电二极管受到光线的激发释放出电荷,感光元件的电信号便由此产生。3….

    2022年6月1日
    36
  • NetXray「建议收藏」

    NetXray「建议收藏」NetXRay是由CincoNetworks公司开发的一个用于高级分组检错的软件,功能很强大。IP地址查询工具。硬件要求硬件要求对硬件要求低,可运行常用的windows平台。主要功能主要功

    2022年7月2日
    21
  • 4g通信系统的网络结构_4g通信

    4g通信系统的网络结构_4g通信1、4G通信网络的关键技术研究4G通信网络,就必须加强对其关键技术的研究,这是决定4G网络通信与3G网络通信不同的关键因素,其主要包括正交频分复用技术、软件无线电技术、智能天线技术、多输入多输出技术、IP核心网技术和多用户检测技术等。1.1正交频分复用技术所谓的正交频分复用技术,简称OFDM技术,是4G通信网络的核心技术,主要是将信道分成若干正交子信道,将高速数据信号转换成并行的低速子数据流,调制到在每个子信道上进行传输。OFDM技术不同于一般性的网络技术,它可以通过相关技术将信号分开,有

    2022年9月15日
    0
  • group by详解

    group by详解一. 概述group_by的意思是根据by对数据按照哪个字段进行分组,或者是哪几个字段进行分组。二. 语法select 字段  from 表名 where  条件  group by    字段或者select 字段  from 表名 group by  字段  having  过滤条件注意:对于过滤条…

    2022年5月26日
    48
  • 用了vue还需要jquery吗_vue与react的区别

    用了vue还需要jquery吗_vue与react的区别⾸先呢jquery他是⽤js封装的⼀个类库,主要是为了⽅便操作dom元素,⽽vue他是⼀个框架,并且呢,他会从真实dom构建出⼀个虚拟的dom树,通过di!算法渲染只发⽣改变的dom元素,其他的相同的dom元素不⽤在重新渲染.⽽使⽤jquery去改变dom元素的时候,即使有相同的dom元素也会重新渲染,jq重点操作dom,而vue重点操作数据。以上就是我对vue和jquery区别的理解….

    2022年10月15日
    0

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号