列车调度 思路解析

列车调度 思路解析火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口(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; 
} 

 

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

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Android实战——ShareSDk的使用,实现一键分享微信好友、朋友圈、QQ

    Android实战——ShareSDk的使用,实现一键分享微信好友、朋友圈、QQShareSDk的使用,实现一键分享微信好友、朋友圈、QQ事先说明:ShareSDK默认QQ可以分享,微信分享则需要在微信的开放平台上认证并申请应用填入对应信息即可微信认证和申请应用涉及到打包和签名APK,请大家自行查询相关资料进行操作关于ShareSDK的开发,参考ShareSDK官网为准欢迎关注CSDN博客:Hensen_的个人主

  • 极限思想之芝诺悖论[通俗易懂]

    极限思想之芝诺悖论[通俗易懂]芝诺悖论是古希腊哲学家芝诺提出的一组悖论。芝诺是一个很有学问,同时也很好玩的人(淘气)。他如果在中国出生,估计很难大学毕业,只能跟池子(脱口秀演员~)一样,高中教室门外面站三年课,然后去讲脱口秀糊口。阿基里斯,大家都知道。古希腊神话中的战神。无论是力量,速度,耐力,格斗技巧,都是巅峰级别的。一夜睡三女,第二天依然可以血染特洛伊的男人。芝诺就提出:在跑步比赛中,如果跑得最慢的乌龟一开始领先…

  • win10开始键没反应解决方法「建议收藏」

    win10开始键没反应解决方法「建议收藏」win10开始键没反应解决方法具体方法如下:1、打开运行窗口。windows7系统:通过“开始”菜单进入。点击“开始”菜单,从打开的菜单中依次点击“所有程序”>“附件”>“运行”来打开“运行”窗口。windows10系统:右击屏幕左下角win标志,在弹出的菜单中找到“运行”,点击进入运行窗口2、在搜索窗口输入“regedit”,打开注册表编辑器。3、在在注册表“HKEY_CLASSES_ROOT”主键下找到“lnkfile”字符串值项。打开它。4、在右侧右击它,会出现一个菜单

  • eclipse的svn使用教程_eclipse svn插件安装

    eclipse的svn使用教程_eclipse svn插件安装  SVN是Subversion的简称,是一个开放源代码的版本控制系统,相较于RCS、CVS,它采用了分支管理系统,它的设计目标就是取代CVS。互联网上很多版本控制服务已从CVS迁移到Subversion。说得简单一点SVN就是用于多个人共同开发同一个项目,共用资源的目的。集中式代码管理的核心是服务器,所有开发者在开始新一天的工作之前必须从服务器获取代码,然后开发,最后解决冲突,提交。所有的版本信…

  • ubuntu下vscode的使用教程_vscode连接ubuntu虚拟机

    ubuntu下vscode的使用教程_vscode连接ubuntu虚拟机1、安装ffmpegwgethttps://ffmpeg.org/releases/ffmpeg-4.1.tar.bz2tar-xjvfffmpeg-4.1.tar.bz2./configure–prefix=/usr/local/ffmpeg–enable-gpl–enable-version3–enable-nonfree–enable-postproc–enable-pthreads–enable-libfdk-aac–enable-libmp3lame

  • 拉格朗日乘子法以及KKT条件

    拉格朗日乘子法以及KKT条件

    2021年11月19日

发表回复

您的电子邮箱地址不会被公开。

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