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

zhangjinxuan

上一关：一元二次方程

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

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

首先，前面说过，每一个大楼都有一个独立的编号 a_i，且按照一定的顺序排列，如 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 <= a_i <= 10^18，保证 a 中元素互不相等，但是不保证 1 <= a_i <= 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. 因为额度原因，部分鱼油可能下一天才能奖励。

                               
登录/注册后可看大图

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

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


本关满意度调查

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-3-21 17:33:03

就这样

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 = ' ')

跳转到最佳答案楼层

zhangjinxuan

顶顶顶 @高山 @tommyyu @sfqxx @元豪

sfqxx

看看

高山

哈哈哈，是不是主题升华太难编了？

zhangjinxuan

高山 发表于 2023-3-20 19:29
哈哈哈，是不是主题升华太难编了？

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

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

元豪

题目到底是什么意思啊什么叫问你这个数组字典序后 d 个排列是多少

元豪

可以搞个样例解释

zhangjinxuan

元豪 发表于 2023-3-20 19:36
题目到底是什么意思啊什么叫问你这个数组字典序后 d 个排列是多少

不知道什么是排列是什么的可能不会怎么理解，稍等，我搞上来吧

高山

zhangjinxuan 发表于 2023-3-20 19:31
你告诉我一个 求排列 的题目怎么编

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

海上小精灵给每一个珊瑚礁（他们的家）排序

zhangjinxuan

高山 发表于 2023-3-20 19:42
海上小精灵给每一个珊瑚礁（他们的家）排序

有道理

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

元豪

zhangjinxuan 发表于 2023-3-20 19:43
有道理

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

神奇!

高山

zhangjinxuan 发表于 2023-3-20 19:43
有道理

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

嗯嗯

额外减小

准备好tle...gogogo
提交后...
全wa

sfqxx

就这样

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 = ' ')

jhq999

sfqxx 发表于 2023-3-21 17:33
就这样

学习
感觉不对
字典排序的话，不是应该11比2小吗？

jhq999

4 1
1 2 3 11
不是应该是
1 3 11 2
不是
1 2 11 3

zhangjinxuan

jhq999 发表于 2023-3-21 18:52
4 1
1 2 3 11
不是应该是

？？？哪里

jhq999

zhangjinxuan 发表于 2023-3-22 07:22
？？？哪里

14楼洛谷通过了，我试了
4 1
1 2 3 11
如果按字典序1 2 3 11后面应该是
1 3 11 2
不应该是
1 2 11 3
因为按字典序
11排在2前面

zhangjinxuan

jhq999 发表于 2023-3-22 08:31
14楼洛谷通过了，我试了
4 1
1 2 3 11

在我的原贴中，哪里有 4 1 1 2 3 11 这个数据???