PTA（栈和队列）2-10 列车调度

zhangzhang2025-11-052025-11-05

2-10 列车调度

分数 6

作者陈越

单位浙江大学

火车站的列车调度铁轨的结构如下图所示。

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

输入格式：

输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：

1 2	9 8 4 2 5 3 9 1 6 7

输出样例：

第一次看这题，我的思路是一个一个放，如果比上一个放的大的就新开一列
我还想着到时候还要比较每一列，想着一列一列比较最大的是谁，好麻烦（后来发现不用想怎么出来，因为只求最少的轨道数量是多少）
于是我就直接问豆包了，发现跟我的思路完全不一样，说用到了贪心算法，第一次遇到这个算法

正确答案

#include <iostream>
#include <vector>
#include <algorithm>  // 用于lower_bound/upper_bound

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> last;  // 存储每条铁轨最后一辆车的序号

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        // 找last中第一个大于x的元素位置（用upper_bound，因为要维护非递增序列）
        auto it = upper_bound(last.begin(), last.end(), x);

        if (it == last.end()) {
            // x比所有铁轨最后一辆车都大，新增铁轨
            last.push_back(x);
        } else {
            // 替换该位置的元素，让铁轨最后一辆车尽可能小
            *it = x;
        }
    }

    // last的长度就是最少铁轨数
    cout << last.size() << endl;

    return 0;
}

这个问题的核心是找到 “最少需要多少条平行铁轨”，本质是求输入序列中最长递增子序列的长度，用贪心 + 二分查找可实现 O (n log n) 的高效解法，完美应对 1e5 的大数据量。

核心思路讲解

要让列车按序号递减从出口离开，意味着每条铁轨上的列车必须是递增排列的（比如铁轨 1：8→9，铁轨 2：4→5→6→7，铁轨 3：2→3，铁轨 4：1）。因为只有每条铁轨递增，才能从后往前（9→8、7→6→5→4、3→2、1）递减驶出。

因此问题转化为：把输入序列划分成最少的递增子序列，而根据 “Dilworth 定理”，最少递增子序列的数量 = 最长递减子序列的长度（或等价于求最长非递增子序列的长度，实际编码中用更易实现的 “维护每条铁轨最后一辆车” 的贪心逻辑）。

具体贪心步骤：

用一个数组last存储每条铁轨最后一辆列车的序号（初始为空）。
遍历每辆待调度的列车x：
- 若x比所有铁轨的最后一辆车都大（即x > last中所有元素）：说明x无法加入任何已有铁轨（会破坏铁轨的递增性），必须新增一条铁轨，将x加入last。
- 若x能加入某条铁轨：找到last中第一个大于x的元素，用x替换它（这是贪心的关键，让后续更小的列车有更多机会加入已有铁轨，减少新增铁轨的数量）。
最终last的长度就是最少需要的铁轨条数。

1.auto是啥

auto 是 C++11 及以上的自动类型推导关键字，核心作用是让编译器根据变量的初始化值，自动判断并推导变量的类型，不用手动写类型名。

关键特点

必须有初始化值（编译器要靠值判断类型），比如 auto it = upper_bound(...) 可行，但 auto a; 报错。
推导结果和手动写类型完全一致，只是简化代码，不改变程序逻辑。

对应代码中的用法

1	auto it = upper_bound(last.begin(), last.end(), x);

这里 upper_bound 的返回值是 vector<int>::iterator（vector 的迭代器类型），手动写很长且容易错。用 auto 后，编译器会自动推导出 it 是迭代器类型，既简洁又不容易出错。

2.`upper_bound(last.begin(), last.end(), x)`是啥

是 C++ 标准库 <algorithm> 中的一个函数，用于在已排序的序列中快速查找，返回 “第一个大于目标值 x 的元素的位置”（迭代器）。

核心要点：

前提：必须作用于非递减排序的序列（如从小到大排列），否则结果无意义。
功能：找到序列中第一个比 x 大的元素，返回其迭代器（可理解为位置指针）。
如果没找到：返回序列的末尾迭代器（如 last.end()），表示所有元素都 ≤ x。

在列车调度代码中的作用：

代码中 last 数组始终保持非递增排序（从大到小），但 upper_bound 仍能正确工作：

当处理列车 x 时，upper_bound(last.begin(), last.end(), x) 会在 last 中找到第一个比 x 大的元素位置。
这个位置就是 x 应该加入的铁轨（替换该位置的元素，保持 last 的有序性，让后续列车能继续高效匹配）。

例如，若 last = [9,5,3,1]，x=6：

upper_bound 会找到第一个比 6 大的元素（即 9），替换后 last 变为 [6,5,3,1]，仍保持非递增。

3.`it == last.end()` 是啥

当 it == last.end() 时，说明当前列车 x 比所有铁轨的最后一辆车都大（或相等），无法加入任何已有铁轨（会破坏铁轨的递增性），因此必须新增一条铁轨，并将 x 作为这条新铁轨的最后一辆车加入 last 数组。

4.*it = x;是啥

迭代器的作用：迭代器是容器提供的一种 “访问接口”，用于遍历容器中的元素，不同容器（如 vector、list、map）有不同的迭代器类型，但用法统一（通过 * 访问元素，通过 ++ 移动位置）。
*it = x 的含义：

这里的 * 是 “解引用操作符”，作用和指针的解引用类似 —— 通过迭代器 it 找到它指向的元素，然后将 x 的值赋给该元素。
在代码中的意义：

当 it 指向 last 数组中 “第一个大于 x 的元素” 时，*it = x 就是用 x 替换这个元素，目的是让当前铁轨的 “最后一辆车” 尽可能小，为后续更小的列车留出更多加入已有铁轨的机会，从而减少总铁轨数量。