双栈排序 luoguAC200 解题报告

首先，这个题爆搜模拟肯定是做不了的（可能有30分） 我们看一看让这个题排序成立的条件的条件： 如果两个数能在一个栈里进行排序，需要满足的条件 - 假设这两个数为$x,y$，位置分别为$i,j,i<j$，需要在$x<y$时满足$j$后面没有比$x$更小的数，因为比$x$更小的数需要在$x$之前出栈，而$y$会妨碍$x$出栈，这时$x$就不能和$y$同栈了，既然他们不同栈，就可以在二分图上连接一条边，最后进行二分图染色就可以了 对于这个题的二分图染色，由于字典序最小，所以要尽可能进1栈，因此，对于没有染色的点而言，染成1，被1遍历到的染成2，被2遍历到的染成1就可以了