【题目大意】
给定一个括号序列，(代表入栈,)代表出栈， 给出一个出入栈顺序和一堆数字，构造一个序列满足任意时刻入栈时序列都是唯一的。
【思路】
对于相同长度的序列，在前面序列相同的情况下最后一个数字保证不同，就可以构造出什么哪些数字是必须互不相同的；完整思路见代码
这里提醒一下别用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;
}