摘要
Title: HJ77 火车进站
Tag: 栈、全排列
Memory Limit: 64 MB
Time Limit: 1000 ms

HJ77 火车进站

题意

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
要求输出所有火车出站的方案，以字典序排序输出。
思路

从小到大全排列所有的出栈序列,并根据入栈序列判断该出栈序列是否正确
具体方法即 check函数，在入栈的同时，去检查出战序列

代码

#include <algorithm>
#include <bits/stdc++.h>
#include <stack>
#include <unordered_map>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int a[N], c[N];

signed main()
{
    // freopen("Tests/input_1.txt", "r", stdin);
    IOS;

    int n;
    cin >> n;
    
    for(int i = 0; i < n; ++ i) cin >> a[i], c[i] = a[i];


    auto check = [&] (int b[]){
        stack <int> st;
        int j = 0;
        for(int i = 0; i < n; ++ i){
            st.push(a[i]);
            while(SZ(st) && b[j] == st.top()){ //实时寻找，因为随时可以弹栈，如果栈顶元素等于出栈序列元素，则栈顶元素出栈并出栈序列下标加1
                st.pop();
                j ++;
            }
        }
        return !SZ(st);
    };

    sort(c, c + n);
    do{
        if (check(c)){
            for(int i = 0; i < n; ++ i) cout << c[i] << " ";
            cout << '\n';
        }
    }while(next_permutation(c, c + n));


    return 0;
}

HJ77 火车进站

题意

思路

代码