题解 | #火车进站#

本题分为两个阶段：

1.首先全排列

2.检查全排列中每一个序列是否合适。

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

//检查当前序列是否合适？这个函数的执行逻辑参考如下：
/*
思路：通过遍历元素出栈顺序来判断是否合法？
我们假设i遍历出栈元素顺序，j用来入栈pushed元素。cur表示当前的出栈元素值
当前出栈元素为cur
栈是否为空？
    空。移动j将元素入栈，直到找到cur或者到达末尾。
        若最终找到了，那么就移动++i，++j。开始新一轮判断
        若j到达了末尾，返回false
    非空。检查cur是否等于栈顶元素
        是。移动++i，++j。开始新一轮判断
        否。移动j，将元素入栈，直到找到cur或者到达末尾
            若最终找到了，就移动++i,++j。开始新的判断
            没找到，就返回false
若循环顺利结束，表明出栈序列遍历到了末尾。满足条件，直接返回true
*/
bool isSuit(vector<int>& pushed, vector<int>& popped) {
    int n = pushed.size(), i = 0, j = 0;
    stack<int> s;
    while (i < n) {
        int cur = popped[i];
        if (s.empty()) {
            while (j < n && cur != pushed[j]) { s.push(pushed[j]); ++j; }
            if (j < n) { ++i; ++j; }
            else return false;
        }
        else {
            if (cur == s.top()) { ++i; s.pop(); }
            else {
                while (j < n && cur != pushed[j]) { s.push(pushed[j]); ++j; }
                if (j < n) { ++i; ++j; }
                else return false;
            }
        }
    }
    return true;
}

//全排列函数。这部分就是一个简单的回溯函数，不多说了。
void pailie(vector<vector<int>>& result, vector<int>& temp, vector<int>& vec) {
    //出口
    if (temp.size() == vec.size()) {
        //检查是否合适？不合适不会加入
        if (isSuit(vec, temp)) result.push_back(temp);
        else return;
    }

    for (auto& i : vec) {
        if (find(temp.begin(), temp.end(), i) != temp.end()) continue;
        temp.push_back(i);
        pailie(result, temp, vec);
        temp.pop_back();
    }
}

int main() {
    //1.输出数据处理
    int numbers; cin >> numbers;
    vector<int> vec(numbers, 0);
    for (int i = 0; i < numbers; ++i) cin >> vec[i];
    //2.进行全排列，并在全排列的顺序中检查是否合理
    vector<vector<int>> result;
    vector<int> temp;
    pailie(result, temp, vec);
    //3.将符合条件的从小到达排列
    sort(result.begin(), result.end());
    for (auto& r : result) {
        for (auto& t : r) cout << t << " ";
        cout << endl;
    }
    return 0;
}