PTA 7-4 列车调度 (25 分)

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：

输入第一行给出一个整数N (2 ≤ N ≤10​5​​)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：

9 8 4 2 5 3 9 1 6 7

输出样例：

4 #include<iostream> #include<stdio.h> #include<set> using namespace std; int main() { int N; cin>>N; const int n = 100000; int num[n]; for(int i = 0;i<N;i++) cin>>num[i]; set<int> s; for(int i = 0;i < N;i++) { if(s.upper_bound(num[i])!=s.end()) s.erase(s.upper_bound(num[i])); s.insert(num[i]); } cout<<s.size()<<endl; return 0; }

使用集合做很简单，当然也可以使用数组来做，大致思路是可以将每条道路的最小序号存储在数组中，每次与数组中的已有的数比较，如果比数组中的数小则替换该数，否则需要再加一条轨道（即添加一个新的数）。注意，查找数组中比输入的数大的数时候，应该采用二分查找，否则会出现运行超时。