题解 | #火车进站#

思路倒是很好想

两点细节：

（1）deque双端队列这是刷了200多道题以来第一次用，记录一下

（2）要求输出时按照字典序，所以我们把它放入set输出（一开始直接放也行，懒得改了）

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<vector<int>>result;
void do_work(stack<int>&st,deque<int>&que,vector<int>&vec,int n);
int main() {
    //第一反应是用一个队列和一个栈
    int n,number;
    deque<int>que;
    while(cin>>n){
        int size = n;
        while(n--){
            cin>>number;
            que.push_back(number);
        }
        stack<int>st;
        int num = que.front();
        que.pop_front();
        st.push(num);
        //准备工作完成
        vector<int>vec;
        do_work(st,que,vec,size);
        //打印结果
        set<vector<int>>m_set(result.begin(),result.end());
        for(auto &i:m_set){
            for(int j = 0;j<size;j++){
                cout<<i[j]<<" ";
            }
            cout<<endl;
        }
    }
}
void do_work(stack<int>&st,deque<int>&que,vector<int>&vec,int n){
    if(vec.size()==n){
        result.push_back(vec);
        return;
    }
    //每轮做两件事，要么从栈里面弹一个到容器；要么把队列的头进栈
    //栈里有值，弹出，回溯
    if(!st.empty()){
        int num = st.top();
        st.pop();
        vec.push_back(num);
        do_work(st, que, vec,n);
        vec.pop_back();
        st.push(num);
    }
    //队列中有值，加入栈，回溯
    if(!que.empty()){
        int num = que.front();
        que.pop_front();
        st.push(num);
        do_work(st, que, vec,n);
        st.pop();
        que.push_front(num);
    }
}
// 64 位输出请用 printf("%lld")