GPLT L2-014 列车调度

题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805063166312448

分析:明显从右到左列车的序号需要依次递减,我们只需要保存每个平行轨道上最尾部的车(也就是序号最小的车就好),如果当前的车比所有轨道尾部车序号都大,开辟一个新的轨道,否则就加进满足条件的轨道里尾部车序号与自己最接近的

这些操作用set可以比较方便的实现

set.rbegin()是当前队列最大值的迭代器,set.upper_bound(t)返回set中第一个比t大的数的迭代器

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int inf=1<<30;
 5 const double pi=acos(-1);
 6 const int mod=998244353;
 7 const int maxn=1e5+7;
 8 const int maxm=6300;
 9 int main(){
10     int n,t;scanf("%d",&n);
11     set<int> s;
12     s.insert(0);//这个0没有任何实际意义,只是为了保证查询能正常进行,所以最后要减1 
13     for(int i=1;i<=n;i++){
14         scanf("%d",&t);
15         if(t<*s.rbegin()){
16             s.erase(*s.upper_bound(t));
17             s.insert(t);
18         }
19         else s.insert(t);
20     }
21     cout<<s.size()-1<<endl;
22     return 0;
23 }

 

上一篇:[Linux] 014 帮助命令


下一篇:B02 - 014、成功后的处理