双栈排序 luoguAC200 解题报告

2018-04-25 15:49:58


首先,这个题爆搜模拟肯定是做不了的(可能有30分)

我们看一看让这个题排序成立的条件的条件:

如果两个数能在一个栈里进行排序,需要满足的条件

  • 假设这两个数为$x,y$,位置分别为$i,j,i<j$,需要在$x<y$时满足$j$后面没有比$x$更小的数,因为比$x$更小的数需要在$x$之前出栈,而$y$会妨碍$x$出栈,这时$x$就不能和$y$同栈了,既然他们不同栈,就可以在二分图上连接一条边,最后进行二分图染色就可以了

对于这个题的二分图染色,由于字典序最小,所以要尽可能进1栈,因此,对于没有染色的点而言,染成1,被1遍历到的染成2,被2遍历到的染成1就可以了