大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口(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
解析:
先将输入的第一个序号放到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账号...