L2-014 列车调度（妙题）

L2-014

解题思路

我们模拟几遍后可以发现：

只有每条轨道最后进去的才用得上。并且新进去的要找到最小的大于它的数（贪心思想），所以每条轨道其实可以只有一个数，这样我们选择用set

可以按这个思路画个图模拟一下

ac✅️代码

#include<iostream>
#include<set>
using namespace std;
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;cin>>n;set<int> tracks;for(int i = 0 ; i < n ;i++){int x;cin>>x;auto it = tracks.upper_bound(x);if(it != tracks.end()){tracks.erase(it);//每放进去一个就要删除之前的tracks.insert(x);//如果找到，合并到该轨道，轨道之前的数不会再用到，直接代替}else tracks.insert(x);//如果没找到，直接插入该数.}cout<<tracks.size()<<endl;return 0;
}