L2-014 列车调度
#include <iostream>
#include <set>
using namespace std;
int main()
{
int n;
cin >> n;
set<int> s;
s.insert(0);
for (int i = 0; i < n; i ++)
{
int a;
cin >> a;
if (a < (*s.rbegin()))
{
s.erase(s.upper_bound(a));
}
s.insert(a);
}
cout << s.size() - 1 << endl;
return 0;
}启示：
用到了set的特性。除了去重之外，还有一个自动按照从小到大排序，和map一样，因为底层是红黑树，一种平衡二叉搜索树。所以可以有rbegin()取最后一个元素，就是最大元素。这里的逻辑就是让每一个轨道都保持一个单调上升的排序，这样再出去的时候就可以按照从大到小排序的出去（从右往左看）。所以对于每一个数来说如果比最大的还要大就单独开一个序列，如果小于最大的，说明可以找到一个序列使得放进去之后组成的排列时单调上升的，为了可以用最少的轨道，这个放进去的序列最好是最后一个数刚好大于要放进去的数，这里使用到了贪心的思想。为了维护每一个单调上升的序列，只要维护一个序列的最后一个值就好，因为前面的值一定比他大，而且不会拿来做比较，所以可以不看，因此set中实际上是维护了一个所有存在的轨道的序列中的最小值的一个不重复集合。而对于要放入的数来说，可以用upper_bound来找到第一个大于他的数，这个数就是要放入的轨道的最后一个值，将当前数放进去，本质上就是在set中将这个最后的值替换。而因为set中没有索引，但是可以自动排序，根据这一特性，为了完成替换这个操作，我们可以将这个最后一个值在set中删去，最后再将a放去set即可，这就在形式上和另外一种情况保持了统一。最后为了保证形式上的统一，不对第一个数特判，即set为空的情况，可以单独放入一个元素0，因为0一定比所有1到n的数小，所以不会被替换，就不会影响答案。最后的答案要求输出轨道的数量，其实就是set中元素的数量，因为有0的存在，所以实际上的答案是s.size() - 1.
题目：
火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式：
输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例：
9
8 4 2 5 3 9 1 6 7
输出样例：
4