#XMOJ12797. 数列压缩
数列压缩
说明
时间限制:1 Sec
内存限制:256 MB
输入文件:compress.in 输出文件:compress.out
小明有一个长度为 $N$ 的数列 $a$,它是 $1,2,\dots,N$ 的一个排列。小明可以对数列进行如下操作:
- 选出一对相邻的元素,满足(左边元素)$<$(右边元素),然后删除这两个元素中的任意一个。
输入格式
第一行一个整数 $N$。
第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。
输出格式
如果无法把数列缩成长度为 $1$,输出 No。
如果可行,第一行输出 Yes;第二行输出 $N-1$ 个用空格隔开的整数。第 $i$ 个整数代表第 $i$ 次操作删掉的数字。
多组合法方案时输出任意一组均可。
样例
样例 1
4
2 3 1 4
Yes
2 1 4
样例说明:
1. 选取相邻 ,删掉 ,数列变为
2. 选取相邻 $(1,4)$,删掉 $1$,数列变为 $(3,4)$
3. 选取相邻 $(3,4)$,删掉 $4$,数列只剩 $(3)$
样例 2
5
5 4 2 3 1
No
样例说明:
一开始只有 这一对满足左 < 右。
- 若先删 $2$,数列变成 $(5,4,3,1)$,之后没有任何满足左 $<$ 右的相邻对,无法继续操作
- 若先删 $3$,数列变成 $(5,4,2,1)$,之后也没有满足左 $<$ 右的相邻对
因此无法缩到长度 $1$。
样例 3
6
3 6 2 5 1 4
Yes
1 5 6 2 4
数据范围
对于 15% 的数据,$N \le 100$。
对于 30% 的数据,$N \le 1000$。
对于 100% 的数据,$2 \le N \le 10^5$,$1 \le a_i \le N$,$i \neq j$ 时 $a_i \neq a_j$。
相关
在下列比赛中: