Skip to content

S2OJ - 1034. 列车调度

题解283 字
# 贪心 # S2OJ # 2018 # 中山集训
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

#输入格式

输入共 22 行：

  • 第 11 行包含 11 个正整数 N，表示 NN 辆列车。
  • 第 22 行包含 NN 个正整数，为 11 至 NN 的一个排列，表示进站次序。

#输出格式

输出共一行，包含一个整数，表示站台内轨道数 KK 的最小值。

#输入样例 1

3
1 2 3

#输出样例 1

3

#输入样例 2

9
1 3 2 4 8 6 9 5 7

#输出样例 2

5

#数据规模与约定

  • 对于 30% 的数据，N≤10N ≤ 10;
  • 对于 70% 的数据，N≤2000N ≤ 2000;
  • 对于 100% 的数据，N≤100000N ≤ 100000;

#思路

贪心解决。

容易想到最优方案是让列车进入队尾车辆编号刚好大于要入队的车的编号的队列，使用 set 维护队尾即可。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int n, l, x, ans;
set<int> s;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        auto it = s.upper_bound(x);
        if (it == s.end()) {
            ans++;
        } else {
            s.erase(*it);
        }
        s.insert(x);
    }
    cout << ans << endl;
    return 0;
}