Skip to content

1261: 双栈排序

题目

题目描述

Tom 最近在研究一个有趣的排序问题。如图所示,通过 2 个栈 $S_1$ 和 $S_2$ ,Tom 希望借助以下 $4$ 种操作实现将输入序列升序排序。

51

  • 操作 1:将输入序列的第一个元素放入栈 $S_1$
  • 操作 2:将输入序列的第一个元素放入栈 $S_2$
  • 操作 3:将 $S_1$ 栈顶元素弹出至输出序列
  • 操作 4:将 $S_2$ 栈顶元素弹出至输出序列

如果一个 $1\sim n$ 的排列 $P$ 可以通过一系列合法操作使得输出序列为 $(1,2,\cdots,n-1,n)$,Tom 就称 $P$ 是一个“可双栈排序排列”。例如 $(1,3,2,4)$ 就是一个“可双栈排序序列”,而 $(2,3,4,1)$ 不是。下图描述了一个将 $(1,3,2,4)$ 排序的操作序列:$\texttt {1, 2, 2, 3, 1, 4, 4, 3}$。

52

注意到,在我们确定了操作 1 和操作 2 的顺序之后,操作3和操作4其实并没有太多的选择。所以我们这里只关注整个操作序列中,由操作 1 和操作 2 构成的子序列,也就是入栈操作序列。对于上面一个例子来说,将 $(1, 3, 2, 4)$ 排序的入栈操作序列就是 $\texttt {1, 2, 2, 1}$

现在,你需要判断一个输入序列能否双栈排序,如果可以,输出字典序最小的入栈操作序列。

输入格式

第一行是一个整数 $n$

第二行有 $n$ 个用空格隔开的正整数,构成一个 $1\sim n$ 的排列,表示输入序列。

输出格式

如果可以按照编号顺序输出,则输出两行,第一行为TAK,第二行为 $n$ 个由空格隔开的整数,表示字典序最小的入栈操作序列。否则输出NIE

样例输入

样例输入 1

text 4 1 3 4 2

样例输入 2

text 4 2 3 4 1

样例输出

样例输出 1

text TAK 1 1 2 1

  • 1号元素进到栈1,然后出来

  • 3号元素进入栈1,

  • 4号元素进入栈2,

  • 2号元素进入栈1,然后出来,接着3号元素出来,4号元素出来

样例输出 2

text NIE

数据范围

时间限制:1000 ms 空间限制:256 mb

一共 25 个测试点每个测试点 $4$ 分,$n$ 取自以下集合 $$ {1, 4, 4, 11, 15, 19, 60, 60, 286, 290, 770, 813, \ 12000, 12196, 12155, 27193, 49126, 49178, \ 69281, 70000, 90000, 96051, 99000, 99838, 100000} $$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!