首先看要求,要用两个栈把一个数组排序成递增数组,有四种操作:
a:将元素压入第一个栈
b:将第一个栈的栈顶元素弹出
c:将元素压入第二个栈
d:将第二个栈的栈顶元素弹出
要求操作的字典序最小
如果无法排成严格的递增序列,那么就输出0
我们可以发现:
如果 i<j<ki < j < ki<j<k 且 ai<aj,ak<aj,ak<aia_i < a_j, a_k < a_j, a_k < a_iai <aj ,ak <aj ,ak <ai 时,那么 aia_iai 和 aja_jaj 就不能在同一个栈里
所以可以用mina记录第i个元素到最后一个元素的最小值,然后套两层for循环,判断连边
然后对这个图进行二分染色,相同颜色的就在同一个栈,第一个染色的一定要在第一个栈,也就是染色为0
然后就可以进行操作了,遍历所有元素:
首先如果第一个栈的栈顶是未排序的元素中最小的就出栈,直到栈顶元素不是未排序元素中最小的
然后判断染色
对于一个栈,如果栈顶元素小于aia_iai 就一直弹出,直到栈顶元素大于aia_iai 后再将aia_iai 压入栈
最后循环弹出剩余的所有元素就行了
如果可以先弹出第一个栈的元素就先弹出第一个栈的元素,保证字典序为最小的
完整代码: