【题目求助】波浪型排列

tcxk 发布于 2020-04-08 10:21， 2159 次点击

波浪型排列
波浪型排列是指，任意三个相邻的数字，中间的数字要么是三者的最大值，要么是三者的最小值。如1,8,2,7,3,5,4,61,8,2,7,3,5,4,6是一个波浪形的排列，而3,2,13,2,1不是。

给定n，将所有长度为n的波浪形排列按照字典序排序。请问排名在k的波浪形排列是多少？

输入格式

第一行：两个整数，表示n和k

输出格式

第一行到第n行：每行一个整数，表示符合要求的一个排列

6 回复

lin51616782020-04-08 10:28

如1,8,2,7,3,5,4,61,8,2,7,3,5,4,6是一个波浪形的排列
8既不是最大也不是最小
是例子错了还是我理解错了?

return_02020-04-08 10:29

回复 2楼 lin5161678

我看是例子错了

tcxk2020-04-08 10:32

例子写错了

lin51616782020-04-08 10:41

最小值是
0101010.......(长度n)

然后加1
(n偶数直接是 010...0k)
(n奇数比较麻烦)

010
011
020
021
030
031
032
033
040......

纠正

10
20
21
30
31
32
40......

尾部2个按照这个次序不停加下去
前缀 n-2个01序列
就得到字典序下一个序列

完成

[此贴子已经被作者于2020-4-8 10:48编辑过]

tcxk2020-04-08 10:44

以下是引用lin5161678在2020-4-8 10:41:55的发言：

最小值是
0101010.......(长度n)

然后加1
(n偶数直接是 010...0k)
(n奇数比较麻烦)
010
011
020
021
030
031
032
033
040......
尾部3个按照这个次序不停加下去
前缀 n-3个01序列
就得到字典序下一个序列

完成

我晕呐，不知道怎么写

lin51616782020-04-08 10:50

输入
10 99
输出
0 1 0 1 0 1 0 1 0 99

输入
9 99
输出
0 1 0 1 0 1 0 14 8