Problem
题目描述
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)排序的操作序列：
Solution
这题我一开始想的是贪心。但后来发现a和c的入栈顺序有误可能会导致无解。
然后我看了一下标签——“图论”？嗯？？？
我看了几个题解。二分图。i与j不能放在一起。贪心。
然后我再试着打了打代码，A了，证明我的思路是正确的。感谢那些题解提供的帮助，虽然我没有完全看懂。
这是一道很巧妙的题目，用了一个我认为很重要的思想。
思路零（最开始的思路）
经过了一些考虑的贪心。
第一，我们如果入这个栈的数是目前排序到的最大的数+1，那么这个栈我们是不是不能再入栈？这是显然的，在这个栈的下一次进栈前，我们应当将这个元素出栈。
第二，否则能入栈则入栈，尽量入a栈。
第三，栈顶的元素必须比入栈的元素要大，正确性显然。
考虑执行顺序b->a->d->c。检查到这种操作能执行则执行。显然这种执行顺序在贪心的求字典序最小上是正确的。
然后这个贪心当然是错误的啦
思路一（来自某题解）
我们先考虑一个栈能不能排。如果一个栈能排的话我们还会用两个栈吗？按照贪心原则，这么做肯定是不行的。
那么问题来了——什么时候我们得必须用两个栈才能排？
引理（来自同样的题解和另一个题解）
在排列P中。若P[k]<P[i]<P[j]，i<j<k，则i和j不能在同一个栈中。正确性不是很显然，感性理解也是可以的。证明可以去网上找其它的题解。想要理解的话不如自己拿个例子试试，比如(2,3,1)。
思路二（来自某题解）
这道题到底跟图论有什么关系？最大的关系在于“双”这个字。
二分图可以用来表示关系的冲突。比如两个相邻的点不能染成同样的颜色，又或是两个数不能放进同一个栈中。知道了这个关系，我们可以知道两个数应该放在什么栈里，知道到底存不存在方案使得排序完成。
我们将这道题转换成二分图进行处理。
枚举\(i<j<n\)，若j+1~n中存在k使得\(P[k]<P[i]<P[j]\)，则i和j连一条边，代表他们不能入同一个栈。
显然若i与j没有连边，就代表他们按顺序排始终可以出现在同一个栈中。
这个过程可以用一个后缀求最小值来\(O(n^{2})\)地求得。
改进后的贪心思路（建立在求得的二分图的基础上）
显然我们现在将图染成了两种颜色。若颜色不同则代表它得入不同的栈。
那么我们考虑一下，顺序是ABC，A是0，B是1，C是0。那么AC肯定入a栈，B入c栈对不对？因为A是最先的。在操作顺序aca和cac中，我们选择前一个操作更好。所以我们可以得到颜色与第一个数同色的点入a栈，其余入c栈。
在入栈的基础上，我们再使用上方的贪心模拟，按照b->a->d->c的操作顺序考虑。显然这种顺序是最优的。并且根据得到的二分图入栈，可以保证顺序是正确的。保证顺序正确得到可行解的同时字典序最小，那么就是题目要求得的解。
何为无解的情况？就是无法构造二分图的情况。即A-B B-C C-A的情况（A-B:A不能和B放在一起）。
个人觉得这题是道很好的拓宽思路的题目2333
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=200010;
int P[N];
int h[N],to[M],nexp[M],p=1;
inline void ins(int a,int b){
nexp[p]=h[a],h[a]=p,to[p]=b,p++;
}
int sm[N];
int color[N];
bool imp;
void dfs(int x,int c){
color[x]=c;
for(int u=h[x];!imp && u;u=nexp[u]){
if(color[to[u]]==-1) dfs(to[u],c^1);
else if(color[x]==color[to[u]]) imp=true;
}
}
int s1[N],t1=1;
int s2[N],t2=1;
int now;
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>P[i];
sm[n]=P[n];
for(int i=n-1;i>=1;i--) sm[i]=min(sm[i+1],P[i]); // 后缀最小值
for(int i=1;i<=n;i++)
for(int j=i+1;j<n;j++)
if(sm[j+1]<P[i]&&P[i]<P[j]) ins(i,j),ins(j,i); // 建图
memset(color,-1,sizeof(color));
for(int i=1;i<=n;i++){
if(color[i]==-1) dfs(i,0); // 进行染色
if(imp) printf("0\n"),exit(0); // 无解则退出
}
int i=1;
now=1;
while(now<=n){
if(s1[t1-1]==now)t1--,now++,printf("b ");
else if(color[i]==0)s1[t1++]=P[i++],printf("a ");
else if(s2[t2-1]==now)t2--,now++,printf("d ");
else if(color[i]==1)s2[t2++]=P[i++],printf("c ");
} // 进行贪心的模拟
return 0;
}