L2-014 列车调度 (25 分)详解

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

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

该题乍看之下不知道是让干什么的,后来我看了别人的博客后才搞懂了这道题的做法。
该题要想让列车按降序输出,那么必须让同一条轨道上的车编号大的先进入,编号小的后进入,而如果一条轨道上编号最小的车的编号如果比要处理的车的编号还要小的话,那么这个该处理的车就必须新开一条轨道去让该车进入,而题目的要求就是要求出需要多少种这样的轨道。从以上分析中,可以得到以下信息:

if(当前编号>所有轨道上的最小编号)
{
	新增轨道并将该编号放入该轨道。
}
else
{
	把该编号放入最接近它的比他稍大一点的轨道中。
	(有同学可能会问为什么要放到最接近他的轨道,这是因为如果有这种情况出现
	{
		输入数据:8 4 2 5 3 9 1 6 
		在编号1进入之前按照伪代码每条轨道是这样过的情况:
		2 4 8
		3 5
		9
		如果将1放到最接近他的第一条轨道中,那么之后的6可以在不增加轨道的情况下放入第三条 
		轨  道,但如果要把1放入第三条轨道,那么就需要再增加一条轨道去放6,显然这样并不是
		最优解。
	})
}

由于该题只需输出轨道数,所以每个轨道上并不需要记录所有的编号,只需要记录最小的编号即可,所以可以用,通过set进行插入删除等操作,至于如何找寻距离编号最近的轨道,可以直接利用lower_bound()函数,极为方便,而且通过set进行的查找时间复杂度低,不易超时,虽然有同学可能会用数组进行二分查找,但显然不如set方便。
下面给出代码

#include<iostream>
#include<set>
using namespace std;
int main()
{
	int n;
	cin>>n;
	set<int>sc;
	for(int i=0;i<n;i++)
	{
		int k;
		scanf("%d",&k);
		set<int>::iterator it=sc.lower_bound(k);
		if(it!=sc.end())
		{
			sc.erase(it);
			sc.insert(k);
		}
		else
		sc.insert(k);
	}
	cout<<sc.size();
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)
blank

相关推荐

  • java字符串类型转换为int_java中double转int类型

    java字符串类型转换为int_java中double转int类型标题Java类型转换:int转double由于double的范围比int数据类型大,所以当int值被赋给double时,java会自动将int值转换为double。隐式转换:由于double数据类型的范围和内存大小都比int大,因此从int到double的转换是隐式的。并不需要像doubletoint转换那样进行类型转换;使用Double.valueOf()方法/***Ja…

  • 零基础学Java(10)面向对象-使用LocalDate类完成日历设计

    零基础学Java(10)面向对象-使用LocalDate类完成日历设计前言在我们完成这个日历设计前,需要了解Java中的预定义类LocalDate的一些用法语法LocalDate.now()//2022-07-01会构造一个新对象,表示构造这个对象时的日期。

  • java extjs 教程_EXTJS入门教程及其框架搭建

    java extjs 教程_EXTJS入门教程及其框架搭建EXTJS是一个兼容AJAX的前台WEBUI的框架,在普通的HTML文件的BODY元素中无须写任何HTML代码,就能产生相应的表格等元素。首先是为每一个页面定义一个类,再以EXTJS的规范格式增加所需的元素,可以使用所见所得的工具:extbuilder来操作,这个类将以XXXXX.js的文件名保存,最后在相应的HTML页面中引入相关的JS和CSS文件:并在BODY中加入下面这段JAVAS…

  • linux 通过crt直接上传和下载文件和文件

    linux 通过crt直接上传和下载文件和文件linux 通过crt直接上传和下载文件和文件

  • windows无法打开图片显示内存不足_Windows图片和传真查看器

    windows无法打开图片显示内存不足_Windows图片和传真查看器解决Windows照片查看器无法显示此图片,因为计算机上的可用内存可能不足解决Windows照片查看器无法显示此图片,因为计算机上的可用内存可能不足问题问题分析解决办法一解决办法二解决Windows照片查看器无法显示此图片,因为计算机上的可用内存可能不足系统:Win10问题最近在使用Windows照片查看器打开一个jpg文件的时候异常Windows照片查看器无法显示此图片,因为计算机上的可用内存可能不足。请关闭一些目前没有使用的程序或者释放部分硬盘空间(如果硬盘几乎已满)

    2022年10月26日
  • JVM – 内存模型

    JVM – 内存模型JVM-内存模型

发表回复

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

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