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)


相关推荐

  • C语言股票交易软件,股票交易系统源程序代码

    C语言股票交易软件,股票交易系统源程序代码#include#include#include#includestructStock{charName[10];intfloatfloat};structStockS[5]={{“桂冠电力”,0},{“华北制药”,0},{“ST金泰”,0},{“伊利股份”,0},{“柳州重工”,0}};flag;//1买入2卖出0都是不Pri[20];Pri…

  • Activiti教程(六)activiti的流程设计_未完待续

    Activiti教程(六)activiti的流程设计_未完待续一.idea配置activiti插件二.流程设计使用idea设计各种流程图并讲解流程空间的各自属性 

  • Laravel 传递数据到视图

    Laravel 传递数据到视图

    2021年10月26日
  • 免费mysql数据库空间_mysql数据库空间满了

    免费mysql数据库空间_mysql数据库空间满了申请地址:https://db4free.net/signup.php在这里注册完并且邮箱认证后即可使用。

  • PHP文件锁

    PHP文件锁一、文件锁是什么?    顾名思义,对文件上锁。    可以通过“进门”的实际情况来理解:    有多个人要通过一个大门到食堂里吃饭,但食堂只有一个座位。     食堂管理员A有点偷懒,不想等那么久,于是就告诉大家,中午都可以来食堂吃饭,但是要跑快点才行,只有一个座位,第一个到的人就可以在食堂吃饭,然后就会锁门,其他人看到门锁上了就哪来的回哪去吧,这…

  • 常用频率频段_常用频段

    常用频率频段_常用频段无线图像传输的常用频率介绍 无线图像传输-常用频率介绍GSM900/1800双频段数字蜂窝移动台核准频率范围: Tx:885~915MHz/1710~1785MHzRx:930~960MHz/1805~1880MHz 说明: 1800MHz移动台传导杂散发射值:1.710~1.755GHz≤-36dBm1.755~12.75GHz≤-30dBm GSM900/180

    2022年10月23日

发表回复

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

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