题解 | #火车进站#

方法：使用双栈（一个正向栈，一个反向栈（vector版））+next_permutation

首先介绍next_permutation: 非常好用的用于输出按字典序的全排列组合。可以对vector，int[]数组等进行重排操作

接下来讲述本题思路：

1. 首先使用反向栈存储车辆编号记录车辆出现顺序trains，这里使用vector将新编号车辆插入头部，每次取最后一个元素，取完pop_back，即可实现
2. 之后对order进行从小到大排序（为了按字典序输出，并输出所有可能序列）
3. 再然后，对于给定反向栈trains与可能序列order，遍历order，

对于某一元素：id：

1. 若栈station为空，则从反向栈trains中取元素放入station中直至出现id，弹出元素并移至下一id
2. 若栈station不空，首先判断id是否为栈station顶端元素，
1. 否：判断id是否仍在trains里
1. 是，执行类似a操作，从trains中取元素放入station直至出现id，弹出元素并移至下一id
2. 否，则说明该order不可能出现
2. 是：弹出栈顶元素，移至下一id

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

bool find(vector<int> trains, int id) {
    if(size(trains) == 0)
        return false;

    for (int i = 0; i < size(trains); i ++) {
        if (id == trains[i])
            return true;
    }
    return false;
}
void show_plans(vector<int> plans){
    for(int i = 0; i < size(plans); i ++)
        cout << plans[i] << " ";
    cout << endl;
}
int main() {

    int nums = 0;
    cin >> nums;

    vector<int> trains;
    vector<int> orders;
    for (int i = 0; i < nums; i ++) {
        int id = 0;
        cin >> id;
        trains.insert(trains.begin(), id);
        orders.push_back(id);
    }
    sort(orders.begin(),orders.end());
    do {
        bool flag = true;
        stack<int> station;
        int len = size(orders);
        vector<int> temp = trains;
        for (int i = 0; i < len; ) {
            int id = orders[i];

            if (station.empty()) {
                int first = temp[size(temp) - 1];
                while (first != id) {
                    station.push(first);
                    temp.pop_back();
                    first = temp[size(temp) - 1];
                }
                temp.pop_back();
                i ++;

            } else {
                if (station.top() != id) {
                    if (find(temp, id)) {
                        int first = temp[size(temp) - 1];
                        while (first != id) {
                            station.push(first);
                            temp.pop_back();
                            first = temp[size(temp) - 1];
                        }
                        temp.pop_back();
                        i ++;
                    }else{
                        flag = false;
                        break;
                    }

                }else{
                    station.pop();
                    i ++;
                }
            }
        }

        if(flag)
            show_plans(orders);
    } while (next_permutation(orders.begin(), orders.end()));
}
// 64 位输出请用 printf("%lld")