当每个元素进哪个栈确定时，不确定的只有某个元素进一个栈，和另一个栈弹出元素的顺序。 这种情况，因为要求字典序最小，而 a 栈的所有操作的字典序都小于 b 栈，我们每次有元素进 b 栈前先尽可能把 a 栈能弹出的先弹出。 这样，我们知道，只要确定每个数进入哪个栈，问题就解决了！ 怎么确定呢？？ 也就是确定哪些元素无论是否同时在栈内，都不能进入同一个栈。即，找到所有 i 元素选择进入 a 栈，那么 j 元素只能进入 b 栈的情况。 如果有一个顺序靠前的元素，和一个顺序靠后的元素，前者大于后者，前者和后者可以进入同一个栈，即前面的元素进入没有弹出时，后面的元素进入。 如果有一个顺序靠前的元素 i，和一个顺序靠后的元素 j，前者大小小于后者

解析： 就算知道是二分图染色还是不会TT。 首先考虑怎么判断是否有解。 a [ i ] 和 a [ j ] 不能压入同一个栈（在同一个栈中出现过）⇔ 存在一个k,使得 i < j < k 且 a [ k ] < a [ i ] < a [ j ] 严格证明就比较复杂了，我就说如何感性理解吧（反正在考场上也没几个人会去严格证明）。 因为一个数只能进出一次，k 要排在前面所以弹出 k 时 i 和 j 都在栈里，如果两者在同一个栈弹出后顺序就错误了，然后找不到除这种情况外的反例，于是就这样了。。。 所以如果输入数据不能使得所有限制成立则无解，然后就可以转化成二分图染色来判定，不能在同一个栈中就连边。 关于输出答案，因为要让字典序最小肯定是尽量加在S1里面，实在不行加进S2。 代码: 欢迎加入团队