先考虑单栈排序。
显然出现231就跪了。
其他情况？
更一般的，若在一个数列中找不到i,j,k满足i<j<k && a[i] < a[j] && a[i] > a[k]，则肯定能够单栈排序。
证明？
首先满足231就肯定不可以。
其他情况呢？
把每个a[i]看成二维的点(i,a[i]),则原来的条件就转化成：……（自己想想吧……不好表述）
于是就可以构造出一种出栈的规则：
对于一段连续上升的就进一个出一个，否则就一直进，最后再出。
于是其他情况都可以了……
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1000 + 9;
int ec,n,a[N],col[N],st1[N],st2[N],Min[N],son[N];
struct edge
{
int link,next;
}es[N*N*2];
inline void addedge(const int u,const int v)
{
es[++ec].next = son[u];
son[u] = ec;
es[ec].link = v;
}
inline void Addedge(const int u,const int v){addedge(u,v);addedge(v,u);}
bool dfs(const int u,const int color)
{
col[u] = color;
for (int i = son[u]; i; i = es[i].next) {
const int v = es[i].link;
if (col[v] != -1) {
if (col[v] != (color^1)) return false;
}
else {
bool t = dfs(v,color^1);
if (!t) return false;
}
}
return true;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("twostack.in","r",stdin);
freopen("twostack.out","w",stdout);
#endif
scanf("%d",&n);
Min[n + 1] = n + 1;
for (int i = 1; i <= n; ++i) scanf("%d",a + i);
for (int i = n; i; --i) Min[i] = std::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] && Min[j + 1] < a[i])
Addedge(i,j);
memset(col,-1,sizeof col);
for (int i = 1; i <= n; ++i)
if (col[i] == -1)
if (!dfs(i,0)) {puts("0");return 0;}
for (int now = 1,i = 1; now <= n; ) {
if (col[i] == 0 && (st1[0] == 0 || st1[st1[0]] > a[i])) {
st1[++st1[0]] = a[i++];
printf("a ");
}
else if (st1[st1[0]] == now) {
--st1[0];
++now;
printf("b ");
}else if (col[i] == 1 && (st2[0] == 0 || st2[st2[0]] > a[i])) {
st2[++st2[0]] = a[i++];
printf("c ");
}else if (st2[st2[0]] == now) {
--st2[0];
++now;
printf("d ");
}
}
}