7-55 列车调度 (25 分)
火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式：
输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例：
1. 9 2. 8 4 2 5 3 9 1 6 7
输出样例：
4
#include<iostream> using namespace std; const int N = 1e5 + 10; int a[N], top, n, x; int l, r, mid;//里面需要用到二分 int main() { cin >> n; while (n--) { cin >> x; if(top == 0 || a[top - 1] < x) { a[top++] = x; } else { l = 0, r = top -1; while (l <= r) { mid = (l + r) / 2; if(a[mid] > x) { r = mid -1; } else { l = mid + 1; } } a[mid] = x; } } cout <<top; return 0; }
c++ stl
#include<iostream> #include<set> using namespace std; int main() { int num,n; cin>>n; set<int> s; for(int i=0;i<n;i++) { cin>>num; if(s.upper_bound(num)!=s.end()) s.erase(s.upper_bound(num)); s.insert(num); } cout<<s.size()<<endl; return 0; }
rbegin（）：
c.begin() 返回一个迭代器，它指向容器c的第一个元素
c.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置
c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素
c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置
upper_bound（）:
upper_bound是找到大于t的最小地址，如果没有就指向末尾
lower_bound是找到大于等于t的最小地址
set：：erase（）：
erase() 迭代器的参数必须是一个指向容器中元素的、有效的、可解引用的迭代器，因此需要确保它不是容器的结束迭代器。这个版本的 erase() 函数会返回一个指向被删除元素的下一个位置的迭代器，如果删除的是最后一个元素，那么它就是结束迭代器。
调用unordered_set容器的成员函数clear()可以删除它的全部元素。成员函数erase()可以删除容器中和传入参数的哈希值相同的元素。另一个版本的erase()函数可以删除迭代器参数指向的元素。
