题目描述
Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a
如果输入序列不为空，将第一个元素压入栈S1
操作b
如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c
如果输入序列不为空，将第一个元素压入栈S2
操作d
如果栈S2不为空，将S2栈顶元素弹出至输出序列
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：<a,c,c,b,a,d,d,b>
当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
输入输出格式
输入格式：
输入文件twostack.in的第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列。
输出格式：
输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
输入输出样例
输入样例#1：
【输入样例1】 4 1 3 2 4 【输入样例2】 4 2 3 4 1 【输入样例3】 3 2 3 1
输出样例#1：
【输出样例1】 a b a a b b a b 【输出样例2】 0 【输出样例3】 a c a b b d
说明
30%的数据满足： n<=10
50%的数据满足： n<=50
100%的数据满足： n<=1000
题解
本蒟蒻刚开始就陷入了贪心的思维，结果30分。。WA
为什么会这样呢？按照贪心的思维，对于当前元素，优先考虑扔进s1，扔不进再考虑弹出s1，弹不出再考虑扔进s2，再考虑弹出s2，还弹不出就无解
看起来很完美= =，实际上暗藏漏洞——这个算法会将一些可行的情况判为无解
因为当你将一个元素扔进s1时，当前是最优了，但这个元素会对之后的元素产生影响，这个是没有考虑进去的，所以这个时候有可能扔进s2才可能有解
具体怎么做呢？
想想，对于扔进同一个栈的两个数A[i] < A[j] 且 i < j，，在j扔进去之前，i一定已经弹出来了，这个时候如果j后面如果还存在这比A[i]小的数，说明A[i]此时不应弹出来，这就形成矛盾了，所以这样的情况i与j不能同时存在于一个栈中
即对于所有i < j && A[i] < A[j],若存在k > j && A[k] < A[i]，则i和j不在同一栈中
由这个关系我们可以利用二分图求解：
对于所有不能存在与同一栈的元素之间连边，对二分图进行一次二分染色【优先染1号色，即入s1栈】，如果染色成功，则有解，且每个数改进哪一个栈也已经确定
最后就是模拟，题目说这是一个1~n的排列= =【一开始没看到弄了好久】，所以我们记录下当前应该弹出哪一个数，
对于进s1的数，能进则进，不能进就弹
对于进s2的数，进之前先看看s1能不能弹【即s1栈顶是不是当前该弹出的数】，再进行s2的操作：能进则进，否则就弹
最后就解出来啦~~
#include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<algorithm> #define LL long long int using namespace std; const int maxn = 1005,maxm = 100005,INF = 2000000000;inline int read(){int out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1;c = getchar();}while (c >= 48 &&c <= 57) {out = out * 10 + c - 48;c = getchar();}return out * flag; }int N,A[maxn],Min[maxn],color[maxn];struct node{int v,id; }e[maxn];inline bool operator < (const node& a,const node& b){return a.v < b.v; }int head[maxn],nedge = 0; struct EDGE{int to,next; }edge[maxm];inline void build(int u,int v){edge[nedge] = (EDGE) {v,head[u]};head[u] = nedge++;edge[nedge] = (EDGE) {u,head[v]};head[v] = nedge++; }void init(){fill(head,head + maxn,-1);N = read();for (int i = 1; i <= N; i++){e[i].v = A[i] = read();e[i].id = i;}Min[N + 1] = INF;for (int i = N; i > 0; i--) Min[i] = min(A[i],Min[i + 1]); }bool flag = true;void dfs(int u,int c){color[u] = c;int to;for (int k = head[u]; k != -1; k = edge[k].next)if (!color[to = edge[k].to]){dfs(to,((c - 1) ^ 1) + 1);if (!flag) return;}else if (color[to] == color[u]){flag = false;return;} }void Build(){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])build(i,j);for (int i = 1; i <= N; i++){if (!color[i]){dfs(i,1);if (!flag) return;}} }const char *alpha = "abcd"; int ans[2 * maxn],ansi = 0; stack<int> s[2];void solve(){int cnt = 1;for (int i = 1; i <= N; i++){if (color[i] == 1){s[0].push(A[i]);ans[++ansi] = 0;}else {s[1].push(A[i]);ans[++ansi] = 2;}while (!s[0].empty() && s[0].top() == cnt){s[0].pop();ans[++ansi] = 1;cnt++;}while (!s[1].empty() && s[1].top() == cnt){s[1].pop();ans[++ansi] = 3;cnt++;}}while (!s[0].empty() || !s[1].empty()){if (!s[0].empty() && s[0].top() == cnt){s[0].pop();ans[++ansi] = 1;cnt++;}if (!s[1].empty() && s[1].top() == cnt){s[1].pop();ans[++ansi] = 3;cnt++;}} }int main(){init();Build();if (!flag) cout<<0<<endl;else {/*for (int i = 1; i <= N; i++) printf("%d ",color[i]);cout<<endl;*/solve();printf("%c",alpha[ans[1]]);for (int i = 2; i <= ansi; i++)printf(" %c",alpha[ans[i]]);printf("\n");}return 0; }