2021牛客暑期多校训练营#10:F-Train Wreck
原题链接:https://ac.nowcoder.com/acm/contest/11261/F
文章目录
- 2021牛客暑期多校训练营#10:F-Train Wreck
-
- 题目大意
- 解题思路
- 代码实现
题目大意
有一个旧火车站,其只有死胡同轨道,可以视为一个栈,可将火车入栈或者出栈。
有 n ( 1 ≤ n ≤ 1 0 6 ) n(1\leq n\leq 10^6) n(1≤n≤106)辆彩色火车进站,第 i i i辆火车的颜色是 k i ( 1 ≤ k i ≤ n ) k_i(1\leq k_i\leq n) ki?(1≤ki?≤n),进出栈顺序已定,现在你需要为每次入栈操作分配一辆火车,使得入栈时栈中其他火车颜色序列唯一。
解题思路
设入栈编号为 1 、 2 、 3 、 4 、 5 、 6 1、2、3、4、5、6 1、2、3、4、5、6。
将它构造成一棵树
祖先节点合法时,当兄弟节点不相同,构造的序列肯定也是合法的所以只需要构造兄弟节点不相同的树。
还可以用向量存储出入时的序列,代替树。
我们不需要知道每个节点的父亲是谁,只要知道它们的兄弟是谁,当存入一个第 i i i层的节点,就将第 i + 1 i+1 i+1层的节点删去,就保证现在第 i i i层存储的是自己的兄弟,可以用向量存储。关于保证目前第 i i i层都是自己的兄弟,因为当自己的父亲被存储,以前存储的非此父节点的子节点都被清除,可得。
用优先队列存储每种颜色的编号和剩余数量,按数量从大到小排序,避免剩下的都是同一种颜色的情况,保证答案最优。
代码实现
#include<bits/stdc++.h>
#define pb push_back
#define pa pair<int,int>
using namespace std;
const int N=1e6+7;
vector<int>ve[N];
priority_queue<pa>qu;
int n,a[N],ans[N];
char c[N<<1];
void rd(int &x){
int res=0;char c=getchar(),last=' ';while(c>'9'||c<'0')last=c,c=getchar();while(c<='9'&&c>='0')res=res*10-'0'+c,c=getchar();x=last=='-'?-res:res;}
void calc(vector<int> a)
{
vector<pa>v;for(auto x:a){
if(qu.empty()){
puts("NO");exit(0);}//为空,表示无颜色可填,输出NOauto u=qu.top();qu.pop();ans[x]=u.second;//记录答案v.pb({
u.first-1,u.second});//数量-1,一起存进队列}for(auto i:v)qu.push(i);
}
int main()
{
rd(n);scanf("%s",c+1);for(int i=1;i<=n;i++){
int x;rd(x),a[x]++;};for(int i=1;i<=n;i++)if(a[i]>0)qu.push({
a[i],i});//优先队列存储编号与数量int top=0,cnt=0;for(int i=1;i<=2*n;i++){
if(c[i]=='(')ve[top++].pb(++cnt),ve[top].clear();//向量存储第top层的儿子elsecalc(ve[top--]);}calc(ve[top]);puts("YES");for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'\n':' ');
}