大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
火车站的列车调度铁轨的结构如下图所示:
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入(一条轨道可以停放多个火车)。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式
输入第一行给出一个整数N (2 ≤ N ≤10000)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例
9
8 4 2 5 3 9 1 6 7
输出样例
4
此题考查的是贪心+二分，核心在于序号小的跟在序号最接近自己且比自己大的列车后面，下面分析来源于参考链接1：
下面是4条用来调度的轨道：
1248 1248
35 —————-> 35
9 7
6 6
当前轨道数len=0
首先8进接着4可以跟在8后面，然后是2。
len=1
现在第一条轨道最后的是2，5肯定不能排在2后面，因为5要比2先出去。所以5进入第二条轨道。现在的状态：(只记录排在轨道最后面的列车)
2
5
len=2
轮到3，3可以排在5后面。
2
3
9比3和2都大，只能进入新的轨道
2
3
9
len=3
1比2，3都小，贪心选择，选最接近的2。于是1进入当前第一条轨道
1
3
9
len=3
6比2，3大
1
3
6
7比1，3，6都大
1
3
6
7
len=4
接着按顺序出去就OK了
代码如下：
#include
using namespace std;
int main(){
int n;
int num[100001];
int len=0;
int k;
cin >> n;
while(n–) {
cin >> k;
if(len==0||num[len-1]
num[len++]=k;
}
else{ //若存在轨道最后一个数大于当前数，利用二分法去最优轨道(轨道最后一个数与当前数的差值最小)
int l=0;
int r=len-1;
int mid;
sort(num,num+len); //保证每个轨道的最后一个数按照从小到大排列
while(l
mid=(l+r)/2;
if(num[mid]>k) r=mid-1;
else l=mid+1;
}
num[l]=k;
}
}
cout << len << endl;
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/159378.html原文链接：https://javaforall.net
