题目描述

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

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

输入格式：

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

输出格式：

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

输入样例：

9
8 4 2 5 3 9 1 6 7

输出样例：

4

思路解析：

首先记录一下这道题学到的有关set的知识点：

这道题以题面给的例子来分析，{8，4，2，5，3，9，1，6，7}按顺序进入轨道。
①首先8进入，因为之前轨道没有任何列车，所以8就直接占用一个轨道a；
②接下来分配4，因为结果要从高到低出轨道，所以每个轨道的列车序号从头到尾也应该呈递减，4可以进入8的轨道a，此时轨道a的末尾元素为4；
③2进入轨道a，a轨道末尾元素为2；
④现在5要分配轨道，但现在有的轨道a末尾元素是2，若5进去则不符合每个轨道都呈递减趋势，所以可知此时5应该去另一条轨道b；
⑤现在a，b轨道末尾元素分别为2,5，故按照递减原则3应该去轨道b，此时b末尾元素变为3；
⑥a、b末尾元素：2,3，此时两个轨道都不符合递减，9应该去新开的轨道c；
⑦a、b、c末尾元素：2,3,9，此时1可去a或b；
⑧6进入轨道c，c末尾元素为6；
⑨a、b、c末尾元素：2,3,6, 7不符合三个轨道，故另开一个轨道d，所以样例输出为四条轨道。

经过上面的分析可知，当一个列车判断进入哪一个轨道时，应该是判断轨道的末尾元素是否大于要插入的列车序列，故不用存每个轨道的所有列车序列，只需要存每条轨道的末尾元素，故使用set容器比较方便，且查找末尾元素可以用set容器的upper_bound()函数。
当有列车插入到非空轨道时，先用upper_bound()函数找到非空轨道的末尾元素并删除，再插入新列车的值即可。

#include<bits/stdc++.h>
using namespace std;
int main() {
  int n, num;
  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);
  }
  printf("%d", s.size());
}