双栈排序
【题目描述】
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希望知道其中字典序最小的操作序列是什么。
【输入】
第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】
输出文件共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；
否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
【题解分析】
二分图即位所有点可以分为两个独立点集。
简单来说就是看是否能把图中的每个点分成两份，连上他们之间的边，不存在三个点之间互相连起的边构成三角形。
而双栈则是要把图中的点都分成两份，看是否满足二分图的性质。
把能进同一个栈的两个元素之间连一条边。
对于i<j<k，使得S[k]<S[i]<S[j].则需要两个栈。若逐一查找，O(n^3)显然不够优秀。
Get优化:动态规划。
能将枚举k转化为O(1)的算法。
这里f[i] = min{s[1],s[2],…,s[i]}转移方程是：f[i] = min{s[i],f[i+1]}.注意要从后往前枚举。
整个算法复杂度是O(n^2).
关于染色
两种颜色，y代表与之相连的一条边，为不构成三角形，y与x应染上不同的颜色。
如果y与x染成不同颜色返回值为0，即不可能，那么y与x不同颜色也不可能。
如果y染成与x相同的颜色，返回值为0.
否则返回值为1
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
const int maxn = 1e3+5;
int n,len,s[maxn],to[maxn],v[maxn];
int s1[maxn],s2[maxn],f[maxn];
struct edge{int y,next;}e[2000005];
inline int read(){
int x = 0,f = 1; char ch = getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f = -1;ch = getchar();}
while(ch>='0'&&ch<='9'){x = x*10 + ch-'0';ch = getchar();}
return x*f;
}
void insert(int xx,int yy){
e[++len].next = to[xx];
to[xx] = len;
e[len].y = yy;
}
bool color(int x,int cl){
v[x] = cl;
for(int i = to[x]; i;i = e[i].next){
int y = e[i].y;
if(!v[y]){
if(!color(y,3-cl)) return 0;
}
else if(v[y] == cl) return 0;
}
return 1;
}
void init(){
n = read();
for(int i = 1;i <= n; i++) s[i] = read();
f[n+1] = INF;
}
int main(){
init();
// memset(v,0,sizeof(v));
for(int i = n; i > 0; i--) f[i] = min(f[i+1],s[i]);
for(int i = 1;i <= n; i++)
for(int j = i+1;j <= n; j++)
if(s[i]<s[j]&&f[j+1]<s[i]) insert(i,j),insert(j,i);
for(int i = 1;i <= n; i++)
if(!v[i])
if(!color(i,1)){puts("0"); return 0;}
int now = 1,t1 = 1,t2 = 1;
for(int i = 1;i <= n; i++){
if(v[i] == 1) printf("a "),s1[++t1] = s[i];
else printf("c "),s2[++t2] = s[i];
while(s1[t1] == now||s2[t2] == now){
if(s1[t1]==now) printf("b "),t1--;
else printf("d "),t2--;
now++;
}
}
return 0;
}