10/30
22:59
OI

[NOIP2008]双栈排序 [二分图][贪心]

双栈排序

考试考了这个题…

考虑问题的简化版本:如果只有一个栈怎么办。可以发现,栈可以进行的事情,就是把原序列划分成若干不相交的段,每一段进行reverse操作。所以,一组形如2,3,1的数据就过不去了。

实际上,如果\exists i < j < k, A_k < A_i < A_j,那么i,j不可以存在于一个栈中。O(n^2)的建立一张对立关系的图并染色,可以判断每个位置可以放在哪个栈中。

然后考虑一个贪心的构造答案。由于加入总是比删除优,我们优先考虑加入,直到栈不满足从底到顶递减。注意A栈比B栈优先级高,需多次检查可否弹出。

代码这里