noip 2008

　　题目链接：http://soj.me/1768

　　刚开始看到这题还以为这是一种排序方式，仔细一看这是一道acm神题啊，好难好难，看了好多别人的代码终于懂了，于是……写个博客装下逼。

　　首先说的是，这题不可贪心，因为贪心法的话总会遇到一种情况——当两个栈都可以放时，不知道放哪个栈，又根据贪心的原则，我们很高兴的把它优先放入了第一个栈，

　　测了一下样例，哇塞对了耶，然后提交，之后就WA了（给跪。。。）

　　这里大概的说一下原因，因为我们优先放入第一个栈，但是不对啊，放入了第一个栈可能导致后面一些东西没地方放，即影响了之后的操作,

　　这里给一个大神提供的样例：7 5 7 2 4 1 6 3 （一般的贪心都会错了吧，感觉。。。）。

　　正确的做法是需要预处理的：

　　首先我们想想单栈排序，我们知道，如果有n个栈，就一定能排序成功，那一个栈呢，什么情况下一个栈无法排序，答案是：

　　如果出现 i < j < k 但是 a[k] < a[i] < a[j] 的情况，则无法单栈排序，至少要两个栈

　　在这里我们可以引入离散数学的二分图思想，如果这个序列能用一个栈排序，则是一分图；如果能用两个栈，则是二分图！

　　不知道说清楚了没……总而言之，就是要建图，将每个数当作一个结点，按某种条件建边，即不能放入同一个栈，之后判断该图是否为二分图，如果是则必然能进行双栈排序！

　　总的来说算法分成了三步：建图 -> 染色 -> 模拟

　　建图

　　一般的做法大概就是用一个三重循环判断各种 i ，j ，k 的组合，但是在这题里面 o( n^3 ) 的时间复杂度会超时，所以我们用一个minx数组进行优化

　　minx[i] 表示第 i 个及 i 之后的所有数字的最小值，我们需要一个for循环来计算minx[0] ~ minx[n-1] ，这是一个 o( n ) 复杂度的操作

　　然后可以进行建图，原来的建图条件可以简化成如果 i < j , minx[j+1] < a[i] < a[j] ，则 i 与 j 之间存在边，这样就是二重循环可以解决的了

　　染色

　　普通的深搜染色，分别染成 1 和 2 ，顺便可以判断一下是否是二分图

　　模拟

　　如果刚刚染色失败了，那就直接输出 0 

　　如果颜色是 1 ，则放进第一个栈，否则进第二个；同时要不断判断栈顶元素是否是该输出的元素

　　

　　po上代码瞧一瞧：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;int n,flag;int a[1010],minx[1010],col[1010];bool map[1010][1010];char st[10010];void color(int index,int c) //对某个点进行染色 { col[index]=c; for (int i=0;i
            
             =0;i--) minx[i]=min(minx[i+1],a[i]); for (int i=0;i
             

s1,s2; for (int i=0;i