巧用set容器 短命女 2022-09-30 12:54 161阅读 0赞 # L2-014. 列车调度 # 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 火车站的列车调度铁轨的结构如下图所示。 ![lp_o9wf01q8p76.jpg][] Figure 两端分别是一条入口(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 #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> using namespace std; int main() { int n,a; scanf("%d",&n); set<int> Set; set<int>::iterator it; for(int i=0;i<n;i++) { scanf("%d",&a); if(Set.empty()) Set.insert(a); else { it=Set.lower_bound(a);//理解为找到比a大的最小数 if(it==Set.end()) Set.insert(a); else { Set.erase(it); Set.insert(a); } } } printf("%d\n",Set.size()); return 0; } [lp_o9wf01q8p76.jpg]: /images/20220705/9dd211173782497ab1c3cfd15085e8e4.png
还没有评论,来说两句吧...