L2-014 列车调度 (25 分)
题目描述
火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
样例
输入格式:
输入第一行给出一个整数N (2 ≤ N ≤10
5
),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式:
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例:
9
8 4 2 5 3 9 1 6 7
输出样例:
4
代码
#include <bits/stdc++.h>
using namespace std;
set<int> s;
//每个轨道只保留序号最低的那个;
//
//如果当前编号大于所有序号, 则只能新开一条轨道
//如果当前编号小于其中的编号, 以为要开辟的轨道数最少, 则将当前编号更新upper_bound;
//
//最后set.size() 为开辟的轨道数量
//每个set的元素相当于一个火车轨道, 存储的是当前轨道的最低编号
int main()
{
int n; cin >> n;
while (n -- )
{
int x; cin >> x;
auto it = s.upper_bound(x); //查找和当前编号最接近的点
if (s.empty() || it == s.end()) s.insert(x);
else if (it != s.end()) //当前编号不为最大
{
s.erase(it); //删除要替换的轨道
s.insert(x); //将当前火车引入
}
}
cout << s.size();
return 0;
}