火车进站题目解析

题目解析：
我看题目的第一眼，理解是1 2 3都进去了，然后都出来了，突然2号车又回来了，先进站，然后到1号车回来了，1进站，最后3进站，这样出站顺序一定有3 1 2了。但是答案不是这样的>_<，只能从答案反推题目完整题意。

题目漏了一个关键的条件：火车站内只有1条铁轨！另外输入数据中的第二行指定了进站顺序，这样所有火车就不能想进站就进站了，要听铁路局指挥安排！所以不能用排列公式直接计算C(3, 3)，只能依次猜测出站的真正可能性，所以初始条件是1 2 3这个顺序就很重要了。

2020.11.8修正：
之前理解不够完善，实际上题目中的火车站内只有1根铁轨，但火车站外有多根铁轨（不然的话整个铁轨就是一条直线了，火车顺序永远只有一种了，这不符合题意），且必须只能按照给定的顺序进站，比如示例1，只能按照1 2 3的顺序进站，意即一定是1号车先进站。但是题目没有规定1出站的时间点，1可以在2进站之后，等2出站了再出站；也可以在2进站之前先出站，这样第1个出站的一定是1号车，顺序必定是1 x x。

所以用穷举列出示例1的所有情形：
1单独先进出的情况，有两种：
1先进站，再出站，然后2进站，3进站，3出战，2出站，出站顺序：1 3 2
1先进站，再出站，然后2进站，2出战，3进站，3出站，出站顺序：1 2 3

1 2先进站，然后2先出站的情况，也有两种：
1先进站，2进站，然后2出站，1出站，3进站，3出站。出站顺序：2 1 3
1先进站，2进站，然后2出站，3进站，3出战，1出站。出站顺序：2 3 1

1 2 3依次全部进站的情况，只能依次出站，只有一种：
1先进站，2进站，3进站，3出站，2出站，1出站。出站顺序：3 2 1

只要满足一点：进站顺序必须满足输入数据的第二行，即永远是1 2 3！

作为火车调度员，每次操作要么入站，要么出站，很明显，我们用递归就可以穷举出所有可能性：

// 火车进站
#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <algorithm>

using namespace std;
vector<vector <int>> answer;

// 火车调度函数，每次调度只有两种情况：进站或出站
void schedule(deque<int> & in, vector<int> & out, stack<int> & station)
{
    if (in.empty() && station.empty()) {
        answer.push_back(out);
        return;
    }

    //进站分支，注意进站分支和出站分支是独立的，因为schedule是递归函数！
    if (!in.empty()) {
        // 保护现场
        auto temp = in.front();

        // 进站
        station.push(in.front());
        in.pop_front();
        schedule(in, out, station);

        // 还原现场
        in.push_front(temp);
        station.pop();
    }

    //出站分支，注意进站分支和出站分支是独立的，因为schedule是递归函数！
    if (!station.empty()) {
        // 保护现场
        auto temp = station.top();

        //出站
        out.push_back(station.top());
        station.pop();
        schedule(in, out, station);

        // 还原现场
        out.pop_back();
        station.push(temp);
    }
}

int main()
{
    auto n = 0;            //火车数量
    auto train_num = 0;    //火车编号

    while (cin >> n) {
        stack<int> station;    // 站内火车栈表
        deque<int> in;        // 等待进站火车队列
        vector<int> out;    // 已出站火车队列

        for (auto i = n; i > 0; i--) {
            cin >> train_num;
            in.push_back(train_num);
        }

        schedule(in, out, station);
        sort(answer.begin(), answer.end());

        for (auto &i : answer) {
            for (auto &j : i) {
                cout << j << " ";
            }
            cout << endl;
        }
        answer.clear();
    }
    return 0;
}