题解 | #火车进站#

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct train {
    int num;        // 列车车次（输入时的编号）
    int entryOrder; // 入栈顺序
};

// 比较函数，按照列车的车次（num）进行字典序排列
bool cmp(const struct train& t1, const struct train& t2) {
    return t1.num < t2.num;
}

// 检查出站序列是否合法
bool isValid(vector<struct train> lst) {
    int n = lst.size();
    vector<bool> out(n, false);  // 记录每辆车的出站状态，out[i]表示入栈顺序为i的车是否出站
    int cur = lst[0].entryOrder;  // 当前列车的入栈顺序
    int last = cur;
    for (struct train car : lst) {
        out[car.entryOrder] = true;
        if (car.entryOrder<last){
            //两辆车出站，这两辆车进站时间进展的车肯定出站了，如果没出站台，说明不合法。
            for(int i = car.entryOrder; i <= last; i++){
                if(!out[i]) return false;
            }
        }
        last = car.entryOrder;
    }
    
    return true;  // 如果所有条件都满足，则该出站序列合法
}

int main() {
    int n;
    while (cin >> n) {
        vector<struct train> list(n);  // 存储列车信息
        for (int i = 0; i < n; i++) {
            cin >> list[i].num;   // 输入列车车次
            list[i].entryOrder = i;  // 记录入栈顺序
        }

        // 按照列车车次的字典序进行排序
        sort(list.begin(), list.end(), cmp);

        // 使用 next_permutation 生成所有可能的排列
        do {
            if (isValid(list)) {  // 检查该排列是否合法
                for (int i = 0; i < n; i++) {
                    cout << list[i].num << " ";  // 输出合法的出站序列
                }
                cout << endl;
            }
        } while (next_permutation(list.begin(), list.end(), cmp));  // 生成下一个排列
    }
    return 0;
}