大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式：
输入第一行给出一个整数N (2 ≤ N ≤)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例：
9
8 4 2 5 3 9 1 6 7
输出样例：
4
样例说明:
第一条轨道:1 2 4 8
第二条轨道:3 5
第三条轨道:6 9
第四条轨道:7 数组长度表示轨道数，火车进站类似于进栈，当轨道里只有一辆车的时候，栈顶即为这辆车，以后还有火车进入轨道，如果火车的编号比任意轨道的栈顶还要大，就新增一条轨道，否则每次从后边来的火车里找到第一个大于栈顶的轨道进入。
数据较大，采用二分查找。
#include using namespace std;
const int maxn = 1e5 + 5;
int main(){
int n;
cin >> n;
int a[maxn];
int len = 0;
for (int i = 0; i < n;i++){
int x;
cin >> x;
if(len==0||a[len-1]> 1;
if(a[mid]>x)
r = mid;
else
l = mid + 1;
}
a[l] = x;
}
}
cout << len << endl;
//system(“pause”);
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/159382.html原文链接：https://javaforall.net
