摘要
Title: L2-014 列车调度 (25 分)
Tag: set
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

L2-014 列车调度 (25 分)

• 题意

  两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

• 思路

  我们需要维护的是各个轨道的出口
  将每个出口放入set中

  • 如果加入的值，在set中有比它大的，那么用它来做这个轨道的下线，大的弹出
  • 如果加入的值，在set中没有比它大的，那么就需要新建轨道

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-04-21 11:37:00
  * @FilePath: \ACM\GPLT\L2-014_.CPP
  * @LastEditTime: 2022-04-21 11:40:30
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  
  set<int> s;
  int n;
  
  signed main()
  {
      IOS;
      cin >> n;
      for (int i = 1; i <= n; ++i)
      {
          int x;
          cin >> x;
          if (s.upper_bound(x) != s.end())
          {
              s.erase(s.upper_bound(x));
          }
          s.insert(x);
      }
      cout << SZ(s);
      return 0;
  }