首页 > 试题广场 >

牛牛摆木棒

[编程题]牛牛摆木棒
  • 热度指数：185 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有n个木棒，长度为1到n。
给定了一个摆放规则。
规则是这样的：对于第i个木棒a_i， && 或 && 。
求满足规则的从小到大的第k个排列是什么呢。

对于两个排列s和t：

如果存在j有任意i<j使得且 ，视为排列s<排列t


示例1

输入

3,3

输出

[2,3,1]

说明

第一小的排列为：[ 1 , 3 , 2 ]
第二小的排列为：[ 2 , 1 , 3 ]
第三小的排列为：[ 2 , 3 , 1 ]
第四小的排列为：[ 3 , 1 , 2 ]
所以答案为：[ 2 , 3 , 1 ]

备注:

算法知识视频讲解
开通博客
头像 GhostLX
发表于 2021-07-17 11:07:51
精华题解 题目陈述 大意：定义波浪形序列为：序列中间的每个数都大于他的相邻的数或者小于他相邻的数。大小定义为字典序大小，求长度为n的序列中第k个波浪型的序列。 算法一：朴素算法 算法思路 一个很显然的思路，就是暴力枚举，字典序递增算出每一个序列，直到第k个 开一个vector来记录当前的序列，第i层代表当 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 诗云panther
发表于 2021-08-15 13:31:53
class Solution {public: /** * * @param n int整型 木棒的个数 * @param k long长整型 第k个排列 * @return int整型vector */ vector<int> sti 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 swm_sxt
发表于 2020-08-06 23:02:00
题意：求n的排列中第k个波浪形的排列 牛客巅峰赛系列里面少有的，还算有一点意思的题目（没错我就是在喷），可惜考场上时间不太够，想出来没码完（好吧确实是因为我一开始把找第k个的部分写麻烦了）。 首先来考虑求满足条件序列数量的问题，记表示长度为n，以k开头的先上升或先下降的序列数量。 预处理出来这个 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 摸鱼学大师
发表于 2021-09-25 20:00:00
题目的主要信息： n根木棒，长度为1到n 对于要求的排列：第根木棒要求或者 求满足条件的排列中从小到大第k个排列 方法一：暴力枚举（超时） 具体做法：我们首先构造一个从1到n的数组，这是这n个数排列的最小值，然后利用next_permutation函数依次构造其余的排列，它会从小到大构造。对于每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Guanngxu
发表于 2021-09-22 17:40:30
题意 该问题让我们求：n 的字典序排列中第 k 个波浪形的排列。什么是波浪形排列呢？即对排列中任意一个数字（除开第一个和最后一个），只能 比 和 都小或者都大。比如2 1 3和1 3 2是波浪形排列，但1 2 3就不是波浪形排列。 DFS 枚举 最容易想到的解决方案是把 n 的所有排列按字典序 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 abcdhhhh
发表于 2021-09-18 17:23:45
题意 称一个 的排列为波浪形的排列当且仅当 ，。求 的第 个波浪形的排列。 解法1：DFS（TLE） 不妨把波列形的排列看成小虫的游走。小虫从 的任意点，任意方向出发，选择前方任意一个未访问过的点，到达后掉头。这样最终产生一个排列。 可以按字典序暴力搜索所有排列，第 个排列即为答案。 下 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

基础数学 排序
难度：
0条回答 806浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号