题解 | #火车进站#

// 思路：用next_permutation遍历所有排列，然后排除不可能的情况
// 不可能的情况：后进的出去后，之前进的不可能先进先出（栈的性质）；如3 1 2和4 2 3 1
// 主要是没有编程难度，思维难度也低
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void print_list(vector<int>& list) {
    for (const auto& i : list) {
        cout << i << ' ';
    }
    cout << endl;
}

int main() {
    int num;
    cin >> num;
    vector<int> trains;
    vector<int> trains_index;
    for (int i = 0; i < num; i++) {
        int temp;
        cin >> temp;
        trains.push_back(temp);
        trains_index.push_back(i);
    }
    
    vector<vector<int>> res;
    vector<int> res_row(num);
    do {
        bool flag = true;
        for (int i = 0; i < num - 2; i++) {
            if (!flag) break;
            int min_train = num + 1;
            for (int j = i + 1; j < num; j++) {
                // 比trains_index[i]大的不计入排序（之后进的不管）
                if (trains_index[j] < trains_index[i]) {
                    // 如果存在增序列则该情况不能实现
                    if (min_train > trains_index[j]) {
                        min_train = trains_index[j];
                    }
                    else {
                        flag = false;
                        break;
                    }
                }
                
            }
        }
        if (flag) {
            for (int i = 0; i < num; i++) {
                res_row[i] = trains[trains_index[i]];
            }
            res.push_back(res_row);
        }
    } while (next_permutation(trains_index.begin(), trains_index.end()));
    sort(res.begin(), res.end());

    for (vector<int>& row : res) {
        print_list(row);
    }
    return 0;
}
// 64 位输出请用 printf("%lld")