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)


相关推荐

  • docker下载安装教程_安卓安装docker

    docker下载安装教程_安卓安装docker前言Docker提供轻量的虚拟化,你能够从Docker获得一个额外抽象层,你能够在单台机器上运行多个Docker微容器,而每个微容器里都有一个微服务或独立应用,例如你可以将Tomcat运行在一个D

  • LNK2001: 无法解析的外部符号的几种情况

    LNK2001: 无法解析的外部符号的几种情况errorLNK2001:无法解析的外部符号无法解析几种情况:1&amp;amp;gt;MSVCRT.lib(MSVCR90.dll):errorLNK2005:_printf已经在libcurl.lib(pqueue.obj)中定义1&amp;amp;gt;MSVCRT.lib(MSVCR90.dll):errorLNK2005:_fprintf已经在libcurl.lib(pem_lib.o…

  • pycharm设置打不开怎么回事_pycharm界面设置

    pycharm设置打不开怎么回事_pycharm界面设置害,pycharm专业版到期了,不能再用了,下了一个社区版,想要编译程序的时候发现没有解释器。解决方法找到设置(右上角,小齿轮)找到项目的Pythoninterpreter设置,点击小齿轮添加新的解释器。选择添加新的interpreter选择对应版本的Python即可。点确定就设置好了。…

  • Android 系统签名打包方法

    Android 系统签名打包方法方式一命令行生成(推荐):此方式不需要配置,步骤也不多。1、在应用程序manifest.xml文件根节点中加入属性:Android:sharedUserId=“android.uid.system”;2、在android系统目录build/target/product/security/拷贝系统签名文件:platform.x509.pem、platform.pk8;3、在out/host/linux-x86/framework目录下找到signapk.jar文件;4、把三个文件(plat

  • Linux shell awk数组使用

    Linux shell awk数组使用awk中使用数组一.数组格式数组是一个包含一系列元素的表.格式如下:abc[1]=”xiaohong”abc[2]=”xiaolan”解释:abc:为数组名称[1]、[2]:为数组元素下标,可以理解为数组的第1个元素、数组的第2个元素”xiaohong”、”xiaolan”:元素内容数组arrray[index-express…

  • Java中@Override的作用「建议收藏」

    Java中@Override的作用「建议收藏」Java中@Override的作用

发表回复

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

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