HJ77 火车进站

Powered by:NEFU AB-IN

Link

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;
  }