先考虑单栈排序。
显然出现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 "); } } }
转载于:https://www.cnblogs.com/lazycal/p/noip2008-t4.html
相关资源：JAVA上百实例源码以及开源项目