分析:方法一:贪心+模拟
显然最后的操作序列的长度一定是(2n),所以我们从前往后填就好了,每一位贪心地,能填(a)就填(a),否则,能填(b)就填(b)....
但要注意一下,有可能出现一个数它同时可以进入两个栈中,根据我们的贪心策略会把它丢入第一个栈中,但是它只有进入第二个栈才合法.这是一种什么情况呢?就是这个元素之后要进栈的元素中有一个比它大的(这个大的比第二个栈的堆顶要大,即这个大的只能压入第一个栈中),且这个比它大的元素后面还有一个比它小的.这种情况我们只能把当前这个元素丢入第二个栈中.所以我们每一次填(a)的时候(check)一下是否是这种情况就好了.
方法二:二分图+模拟
上面那种需要特别(check)的情况是这样的,(i<j<k)且(a_k<a_i<a_j),这种情况下(i,j)不能在一个栈中,所以我们在(i,j)之间连边,我们把所有的这种关系够连边之后,就构成了一张二分图,二分图的两边的点集就分别是两个栈中的元素.模拟一下就好了.
方法二为口胡,无代码.且下面的代码只能保证能过洛咕数据,因为我在(UOJ)上莫名玄学交不了这道题.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1005;
int n,now1,now2,top1,top2,a[N],st1[N],st2[N];
char ans[N];
inline bool check(int i){
if(!top2)return 1;int j,k;
for(j=i+1;j<=n;++j)if(a[j]>a[i]&&a[j]>st2[top2])break;
for(k=j+1;k<=n;++k)if(a[k]<a[i])return 0;
return 1;
}
int main(){
n=read();for(int i=1;i<=n;++i)a[i]=read();
now1=1,now2=1,st1[0]=n+1,st2[0]=n+1;
for(int i=1;i<=(n<<1);++i){
if(now1<=n&&a[now1]<st1[top1]&&check(now1)){
st1[++top1]=a[now1];++now1;
ans[i]='a';continue;
}
if(st1[top1]==now2){
--top1;++now2;
ans[i]='b';continue;
}
if(now1<=n&&a[now1]<st2[top2]){
st2[++top2]=a[now1];++now1;
ans[i]='c';continue;
}
if(st2[top2]==now2){
--top2;++now2;
ans[i]='d';continue;
}
puts("0");return 0;
}
for(int i=1;i<=(n<<1);++i)printf("%c ",ans[i]);
printf("
");
return 0;
}