鱼C论坛

 找回密码
 立即注册
查看: 2115|回复: 19

[已解决]【C++板块提升计划】梦想护卫舰 第29期 排列 & 鱼CR1 B题题解【原创】

[复制链接]
发表于 2023-3-20 18:15:38 | 显示全部楼层 |阅读模式
本帖最后由 zhangjinxuan 于 2023-3-22 18:09 编辑


上一关:一元二次方程

梦想护卫舰 第29关 排列 & 鱼CR1 B题题解


题目描述
你们了解了海上城市,但目前这个海上城市正面临一个问题

首先,前面说过,每一个大楼都有一个独立的编号 ai,且按照一定的顺序排列,如 3 4 1, 1 9 8 2

但当地的人不乐意了,偏要把这个排列改成后 d 个的排列(按字典序),如 3 4 1 的后 1 个排列是 4 1 3

现在给你 n, d,和现在海上城市的排列,你能求出改成后 d 个的排列吗?

如果没有后 d 个排列,请输出字典序最大的排列

输入格式

第一行两个数字 n,d,第二行 n 个数字,表示整个数组

输出格式
n 个数字,表示答案

输入样例1
3 3
1 2 3

输出样例1
2 3 1

输入样例2
3 3
3 1 2

输出样例2
3 2 1

解释
1 2 3 的排列如下(按字典序排列):
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
可以发现,1 2 3 后 3 个排列是 2 3 1,3 1 2 没有后 3 个排列,只能是字典序最大的排列(3 2 1)

数据范围
对于 100% 的数据,保证 1 <= n <= 2000, 0 <= d <= 5000, 1 <= ai <= 10^18,保证 a 中元素互不相等,但是不保证 1 <= ai <= n


                               
登录/注册后可看大图


注:本题原创,链接:https://www.luogu.com.cn/problem/U287187


                               
登录/注册后可看大图


答案与解析
游客,如果您要查看本帖隐藏内容请回复
[/hide]

最佳战士排行榜
第一名第二名第三名
名字sfqxx
语言Python
代码得分100
奖励5鱼币5荣誉+“最佳答案”3鱼币3荣誉2鱼币2荣誉


我们一起来 Hack

Hack 规则
1. Hack 经证实均有奖励,你在 Hack 时得提供完整证据、证明;
2. 在本关,支持题面 hack,标程 hack,细节问题奖励 1~5 鱼币,重点问题奖励 5~10 鱼币
3. 奖励上限为 3


名字jhq999
Hack 类型未知
是否证实证实中
奖励暂无


答题/奖励规则
1. 不能抄袭,否则无奖励,可能还会扣分;
2. 当您遇到问题时,您可以回贴提问,我会为您解答
3. 提供完整能得分的题解,均有奖励
4. 因为额度原因,部分鱼油可能下一天才能奖励。


                               
登录/注册后可看大图


想查看更多精彩内容,请访问 本专辑

创作不易,如果你喜欢,别忘了分、顶


本关满意度调查
最佳答案
2023-3-21 17:33:03
本帖最后由 sfqxx 于 2023-3-21 17:34 编辑

就这样
def next_permutation() -> bool:
    pos = int(1145141919810)
    for i in range(n - 2, -1, -1):
        if a[i + 1] > a[i]:
            pos = i
            break
    else:
        return False
    for i in range(n - 1, pos, -1):
        if a[i] > a[pos]:
            a[i], a[pos] = a[pos], a[i]
            break
    l = pos + 1
    r = n - 1
    while l <= r:
        a[l], a[r] = a[r], a[l]
        l += 1
        r -= 1
    return True

n, d = map(int, input().split())
a = list(map(int, input().split()))
for i in range(0, d):
    if next_permutation() == False:
        break
for i in a:
    print(i, end = ' ')
多选投票: ( 最多可选 6 项 ), 共有 1 人参与投票
您所在的用户组没有投票权限

点评

我很赞同!: 5.0
我很赞同!: 5
今天偷懒一下  发表于 2023-3-21 20:06

评分

参与人数 2荣誉 +4 贡献 +3 收起 理由
myd0313 + 1 无条件支持楼主!
sfqxx + 3 + 3 鱼C有你更精彩^_^

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-3-20 19:15:59 | 显示全部楼层

评分

参与人数 1鱼币 +1 收起 理由
myd0313 + 1 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-20 19:21:06 From FishC Mobile | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-20 19:29:28 From FishC Mobile | 显示全部楼层
哈哈哈,是不是主题升华太难编了?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-3-20 19:31:23 | 显示全部楼层
高山 发表于 2023-3-20 19:29
哈哈哈,是不是主题升华太难编了?

你告诉我一个 求排列 的题目怎么编

或者说,给你一个“海上城市”的1~N排列,问这个下一个排列???
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-20 19:36:52 | 显示全部楼层
题目到底是什么意思啊什么叫问你这个数组字典序后 d 个排列是多少
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-20 19:37:29 | 显示全部楼层
可以搞个样例解释
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-3-20 19:38:11 | 显示全部楼层
元豪 发表于 2023-3-20 19:36
题目到底是什么意思啊什么叫问你这个数组字典序后 d 个排列是多少

不知道什么是排列是什么的可能不会怎么理解,稍等,我搞上来吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-20 19:42:01 From FishC Mobile | 显示全部楼层
zhangjinxuan 发表于 2023-3-20 19:31
你告诉我一个 求排列 的题目怎么编

或者说,给你一个“海上城市”的1~N排列,问这个下一个 ...

海上小精灵给每一个珊瑚礁(他们的家)排序
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-3-20 19:43:24 | 显示全部楼层
高山 发表于 2023-3-20 19:42
海上小精灵给每一个珊瑚礁(他们的家)排序

有道理

为了与前面的“海上城市”串联起来,就城市吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-20 19:44:26 | 显示全部楼层
zhangjinxuan 发表于 2023-3-20 19:43
有道理

为了与前面的“海上城市”串联起来,就城市吧

神奇!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-20 19:44:57 From FishC Mobile | 显示全部楼层
zhangjinxuan 发表于 2023-3-20 19:43
有道理

为了与前面的“海上城市”串联起来,就城市吧

嗯嗯
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-21 06:20:02 | 显示全部楼层
准备好tle...gogogo
提交后...
全wa
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-21 17:33:03 | 显示全部楼层    本楼为最佳答案   
本帖最后由 sfqxx 于 2023-3-21 17:34 编辑

就这样
def next_permutation() -> bool:
    pos = int(1145141919810)
    for i in range(n - 2, -1, -1):
        if a[i + 1] > a[i]:
            pos = i
            break
    else:
        return False
    for i in range(n - 1, pos, -1):
        if a[i] > a[pos]:
            a[i], a[pos] = a[pos], a[i]
            break
    l = pos + 1
    r = n - 1
    while l <= r:
        a[l], a[r] = a[r], a[l]
        l += 1
        r -= 1
    return True

n, d = map(int, input().split())
a = list(map(int, input().split()))
for i in range(0, d):
    if next_permutation() == False:
        break
for i in a:
    print(i, end = ' ')

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zhangjinxuan + 5 + 5 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-21 18:45:59 | 显示全部楼层
本帖最后由 jhq999 于 2023-3-21 18:49 编辑


学习
感觉不对
字典排序的话,不是应该11比2小吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-21 18:52:25 | 显示全部楼层
4 1
1 2 3 11
不是应该是
1 3 11 2
不是
1 2 11 3
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-3-22 07:22:48 From FishC Mobile | 显示全部楼层
本帖最后由 zhangjinxuan 于 2023-3-22 07:25 编辑
jhq999 发表于 2023-3-21 18:52
4 1
1 2 3 11
不是应该是


???哪里
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-3-22 08:31:21 | 显示全部楼层

14楼洛谷通过了,我试了
4 1
1 2 3 11
如果按字典序1 2 3 11后面应该是
1 3 11 2
不应该是
1 2 11 3
因为按字典序
11排在2前面
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-3-22 18:08:01 | 显示全部楼层
jhq999 发表于 2023-3-22 08:31
14楼洛谷通过了,我试了
4 1
1 2 3 11

在我的原贴中,哪里有 4 1 1 2 3 11 这个数据???
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 21:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表