一道远古时期的联赛题，比较经典。 由于联赛快到了，这里就写一写有理有据的思考过程： 首先，这种题目应该手玩几次。我们想让字典序最小，肯定尽量往 S1 放。而什么时候需要用第二个栈呢？所以我们考虑当只有一个栈时，什么情况下不能排序。自己试一试之后，发现只有这种情况： 存在 i<j<k, ak<ai<aj, 要先出来，导致 j 不能在 i 之后出栈。可以发现没有其他情况会导致无解。 所以这样的i, j 一定不能放在同一栈中。 所以我们可以 O(n2) 得到所有约束。 01 染色之后就能判无解，并得到两个需要放在不同栈的集合。剩余的其他点就放到 S1 。 知道放哪个栈就很简单了，模拟即可，字符小的操作优先。
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int maxn=1005,maxe=maxn*maxn; int n,a[maxn],_min[maxn],c[maxn]; int fir[maxn],nxt[maxe],son[maxe],tot; bool vis[maxn]; void add(int x,int y){ son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot; } void dfs(int x){ for(int j=fir[x];j;j=nxt[j]) if(c[son[j]]==-1) c[son[j]]=c[x]^1, dfs(son[j]); else if(c[son[j]]==c[x]) printf("0\n"),exit(0); } int stk1[maxn],stk2[maxn],top1,top2; int main(){ freopen("hh.in","r",stdin); freopen("hh.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); _min[n+1]=1e9; for(int i=n;i>=1;i--) _min[i]=min(_min[i+1],a[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[i]<a[j]&&a[i]>_min[j+1]) add(i,j), add(j,i), vis[i]=vis[j]=true; memset(c,255,sizeof(c)); for(int i=1;i<=n;i++) if(vis[i]){ if(c[i]==-1) c[i]=0, dfs(i); } else c[i]=0; int top_out=1,top_in=1; while(top_out<=n){ if(stk1[top1]==top_out) printf("b "), top1--, top_out++; else if(c[top_in]==0) printf("a "), stk1[++top1]=a[top_in++]; else if(stk2[top2]==top_out) printf("d "), top2--, top_out++; else if(c[top_in]==1) printf("c "), stk2[++top2]=a[top_in++]; } return 0; }