L2-014 列車調度（隊列模擬:set）

題意：

兩端分別是一條入口（Entrance）軌道和一條出口（Exit）軌道，它們之間有N條平行的軌道。每趟列車從入口可以選擇任意一條軌道進入，最后從出口離開。在圖中有9趟列車，在入口處按照{8，4，2，5，3，9，1，6，7}的順序排隊等待進入。如果要求它們必須按序號遞減的順序從出口離開，則至少需要多少條平行鐵軌用于調度？

思路：

這題如果直接用隊列模擬會內存超限并超時，沒有必要存儲每個隊列的所有值，事實上只要存儲每個隊列的隊尾值即可，但是這樣做還是會超時，所以用set存儲所有隊列的隊尾值并每次查找第一個大于新值的的位置進行操作即可，一開始先插入0，每次set的rbegin()是當前最大值，直接與新值比較節約很多時間。

#include<bits/stdc++.h>
using namespace std;
set<int> s;int main(){int n,t;scanf("%d",&n);s.insert(0);for(int i=0;i<n;i++){scanf("%d",&t);if(t<*s.rbegin()){s.erase(s.upper_bound(t));}s.insert(t);}cout<<s.size()-1<<endl;return 0;
}

?