网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[NOIP2008]双栈排序
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 09:00 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 09:00 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 09:00 |
输入文件 | twostack.in | 输出文件 | twostack.out |
【问题描述】
Tom最近在研究一个有趣的排序问题。如图所示,通过2个栈S1和s2,Tom希望借助以下4种操作实现将输入序列升序排序。
-
操作a
- 如果输入序列不为空,将第一个元素压入栈Sl
-
操作b
- 如果栈S1不为空,将Sl栈顶元素弹出至输出序列
-
操作c
- 如果输入序列不为空,将第一个元素压入栈s2
-
操作d
- 如果栈S2不为空,将S2栈顶元素弹出至输出序列
如果一个l~n的排列P可以通过一系列操作使得输出序列为l,2,…,(n-1),n,Tom就称P是一个“可双栈排序排列”。例如 (1,3,2,4)就是一个“可双栈排序排列”,而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序 列:
当然,这样的操作序列有可能有多个,对于上例(1,3,2,4),是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
【输入】
输入文件twostack.in的第一行是一个整数n。
第二行有n个刚空格隔开的正整数,构成一个1~n的排列。
【输出】
输出文件twostack.out共一行,如果输入的排列不是“可双栈排序排列”,输出数字0;
否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。
【输入输出样例1】
twostack.in
4 1 3 2 4
towstack.out
a b a a b b a b
【输入输出样例2】
twostack.in
4 2 3 4 1
towstack.out
0
【输入输出样例3】
twostack.in
3 2 3 1
towstack.out
a c a b b d
【限制】
- 30%的数据满足: n<=10
- 50%的数据满足: n<=50
- 100%的数据满足:n<=1000