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
