Skip to content
本博客自 2023 年 4 月 4 日起转为归档状态，可能不再发表新的博文。点此了解博主的竞赛生涯。
This blog has been archived by the owner since April 4, 2023. It may no longer have new updates.

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;
}