牛客网 火车出站 dfs+模拟+栈

题目链接

dfs实现全排列，再用模拟的方法，判断每种情况是否能符合出栈顺序。

因为没注意输入的值不一样，输出按照字典序，自己在坑里转了好久。

顺带一题，好像不用去重，也就是说，或许数据存在编号相同的火车，但是实际上不一样。

#include <iostream>
#include <algorithm>
#include <stack>
#include <cmath>
#include <set> 
using namespace std;
int n;
const int maxn = 11;
int arr[maxn];
int vis[maxn];
int stc[maxn];
int top;
int cnt[maxn];
multiset<int> set1;
bool judge2(int cnt[],int cnt2[]){
    for(int i = 0;i<n;++i){
        if(cnt[i]!=cnt2[i]){
            return false;
        }
    } 
    return true;
}
bool judge(){
    stack<int> s;
    int a=0;
    for(int i = 0 ; i<n ;++i){
        s.push(arr[i]);
        while(!s.empty() && s.top()==stc[a]){
            s.pop();
            a++;    
        }
    }
    if(!s.empty()){
        return false;
    }else {
        return true;
    }
    return true;
}
void init(){
    for(int i = 0;i<maxn;++i){
        vis[i] = 0;
        cnt[i] = 0;
    }
    return ;
}
void dfs(int ith){
    if(ith == n){
        if(judge()){
            int ans = 0;
            int k = 1;
            for(int i = n-1; i>=0;--i){
                ans += stc[i]*k;
                k*=10;
            }        
            set1.insert(ans);        
        }     
        return ;
    }
    for(int i = 0;i < n; ++i){
        if(vis[i] == 0){
            vis[i] = 1;
            stc[top++] = arr[i];
            dfs(ith+1);
            vis[i] = 0;
            top--;            
        }
    }
    return ;
}
int main(){
    while(cin>>n){
        init();
        set1.clear();
        for(int i =0;i<n;++i){
            cin>>arr[i];
            cnt[arr[i]]++;
        }
        init();
        top = 0;
        dfs(0);        
        multiset<int> :: iterator it;
        int stc2[maxn];
        for(it = set1.begin();it!=set1.end();it++){
            int num1 = *it;
            top = 0;
            while(num1){
                stc2[top++] = num1%10;
                num1 /= 10;
            }
            for(int i = n - 1;i>=0;--i){
                if(i == n-1){
                    cout<<stc2[i];
                }else {
                    cout<<" "<<stc2[i];
                }
            }
            cout<<endl;
        }
    }
    return 0;
}