Train Wreck

【题目大意】
给定一个括号序列，(代表入栈,)代表出栈， 给出一个出入栈顺序和一堆数字，构造一个序列满足任意时刻入栈时序列都是唯一的。
【思路】
对于相同长度的序列，在前面序列相同的情况下最后一个数字保证不同，就可以构造出什么哪些数字是必须互不相同的；完整思路见代码
这里提醒一下别用map，会卡时间，这里卡了我好久，反复算复杂度都没发现；
【代码】

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e6 + 7;
ll mp[maxn];
ll col[maxn];
ll ans[maxn];
struct node {
    ll x;
    ll cnt;
    bool operator<(const node &x) const {
        return cnt < x.cnt;
    }
};
vector<ll> m;
priority_queue<node> q;
ll n;
char s[2 * maxn];
vector<ll> v[maxn];
vector<ll>p;
int main() {
    cin>>n;
    string s;
    cin>>s;
    int num = 0;
    int l = 0;
    for (ll i = 0; i < 2 * n; i++) {
        if (s[i] == ‘(‘) {
            l++;
            num++;
            v[mp[l - 1]].push_back(num);
            mp[l] = num;
        } else {
            l--;
        }
    }
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin>>x;
        col[x]++;
    }
    for(ll i=1;i<=n;i++)
    {
        if(col[i]!=0)
        {
            q.push({i,col[i]});
        }
    }
    for(ll i=0;i<=n;i++)
    {
        if(v[i].size()>0)
        {
            p.push_back(i);
        }
    }
    stack<node> sta;
    for (ll i = 0; i <p.size(); i++) {
        if (v[p[i]].size() >0)
            {
            // vector<node>now;
            for (ll j = 0; j < v[p[i]].size(); j++) {
                if (q.empty()) {
                    cout<<"NO\n";
                    return 0;
                } else {
                    node vv = q.top();
                    ans[v[p[i]][j]] = vv.x;
                    q.pop();
                    vv.cnt--;
                    if (vv.cnt > 0) {
                        sta.push(vv);
                    }
                }
            }
            while (!sta.empty()) {//为保证不同,处理完一个序列后再将剩余数字加入
                q.push(sta.top());
                sta.pop();
            }
        }
    }
    cout<<"YES\n";
    for (ll i = 1; i <= n; i++) {
        if (i != n)
           cout<<ans[i]<<" ";
        else
           cout<<ans[i]<<endl;
    }

    return 0;
}

Train Wreck

原文：https://www.cnblogs.com/DurKui/p/15154610.html