pta 列车调度_数据结构/PTA-列车调度/栈/数组

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

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

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

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

pta 列车调度_数据结构/PTA-列车调度/栈/数组

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

输入格式:

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

输出格式:

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

输入样例:

9

8 4 2 5 3 9 1 6 7

输出样例:

4

分析:出这道题的人的语文成绩估计一塌糊涂……

可以这么理解题意:原本,只有一条连接出入口的轨道。现在,由于好几辆车都不是顺序驶入,却还要求他们降序驶出,所以需要另开出其他轨道供它们                   走,使得它们能降序驶出。(但原有轨道应算在结果里)

想让列车按降序输出,那么必须让同一条轨道上的车编号大的先进入,编号小的后进入,而如果一条轨道上编号最小的车的编号如果比要处理的

车的编号还要小的话,那么这个该处理的车就必须新开一条轨道去让该车进入。

样例中输出的结果应该是   8   4   2   1——————

5   3——————————

9   6——————————

7————————————

1、考虑使用二分法

2、使用set容器

先将一个数插入进set容器中,set容器默认从小到大(自动排序);

依次进行每个数的输入,如果输入的数比当前set容器中的最后一个数小,删除set容器中第一个大于输入数的值,再将输入数进行插入,

重新排序后,输入的值就代替了删除的值,依次循环往复,进行到结尾 。

代码

二分法做法:

#include

using namespacestd;intmain()

{intn;

scanf(“%d”,&n);int a[100005]= {0}; //最大到十万

int i,sum=0;intx;for(i=0;i

{

scanf(“%d”,&x);if(sum==0||a[sum-1]

{

a[sum]=x;

sum++;

}else //该车比前车小,考虑是跟着前车的路,还是跟着其它比它大的车的路

{ //二分查找,找大于该车的最小编码车

int p=0;int q=sum-1;while(p

{int mid=(p+q)/2;if(a[mid]==x)break;else if(a[mid]>x)

q=mid-1;elsep=mid+1;

}

a[p]=x;

}

}

printf(“%d”,sum);

}

set做法:

#include

using namespacestd;intmain()

{int a[100001]={0};sets;intn;

scanf(“%d”,&n);for(int i=1;i<=n;i++){

cin>>a[i];

}for(int i=1;i<=n;i++){if(s.upper_bound(a[i])!=s.end()){

s.erase(s.upper_bound(a[i]));

s.insert(a[i]);

}elses.insert(a[i]);

}

cout<

}

https://blog.csdn.net/qq_40160605/article/details/80150252

https://blog.csdn.net/suguoliang/article/details/88592304

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

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

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

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

(0)
blank

相关推荐

  • ajax跨域的解决办法_java如何解决跨域问题

    ajax跨域的解决办法_java如何解决跨域问题什么是跨域问题?跨域问题来源于JavaScript的”同源策略”,即只有协议+主机名+端口号(如存在)相同,则允许相互访问。也就是说JavaScript只能访问和操作自己域下的资源,不能访问和操作其他域下的资源。跨域问题是针对JS和ajax的,html本身没有跨域问题。查看浏览器开发者工具Console报错:Failedtoloadhttp://a.a.com:8080/A/FromServlet?userName=123:No‘Access-Control-Allow-Origin’

  • 关于iPhone尺寸与分辨率[通俗易懂]

    浅谈不同型号iPhone的尺寸与不同的分辨率首先谈谈编者对分辨率这个概念的认知,分辨率与清晰度挂钩,同样尺寸的视图,分辨率越高清晰度越好。另外还要引出一个重要的概念:PPI(pixelsperinch)PPI是图像分辨率的单位,图像PPI值越高,画面的细节就越丰富,因为单位面积的像素数量越多,一般PPI>300人眼难以分辨出来。分辨率分为水平和垂直两种,

  • 《通信之道》导读

    《通信之道》导读

  • 罗马时钟代码

    罗马时钟代码先看看效果图第一部分HTML页面代码<!DOCTYPEhtml><htmllang=”en”> <head> <metacharset=”UTF-8″> <metaname=”viewport”content=”width=device-width,initial-scale=1.0″> <met…

  • awvs14安装教程_极品飞车14迅雷下载

    awvs14安装教程_极品飞车14迅雷下载Awvs14.1.210329187更新日期为2021年5月4日。首先卸载旧版awvs,然后重启电脑下载地址:Awvs14.1.210329187安装新版本运行AcunetixPremiumv14.2.210503151.exe。到如下填写登录的用户名和密码安装完后如下,此时没有激活激活安装完成后运行AcunetixPremiumActivationTool.exe进行激活,如下已经成功激活,然后改成中文版,如下,右上角点击保存既可以…

  • 详解Element.scrollIntoView()

    详解Element.scrollIntoView()Element.scrollIntoView()方法让当前的元素滚动到浏览器窗口的可视区域内。语法element.scrollIntoView();//等同于element.scrollIntoView(true)element.scrollIntoView(alignToTop);//Boolean型参数element.scrollIntoView(scrollIntoViewOptions);//Object型参数参数alignToTop可选一个Boolean值

发表回复

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

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