zhangjinxuan 发表于 2023-3-20 18:15:38

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

本帖最后由 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

static/image/hrline/1.gif

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

static/image/hrline/1.gif

答案与解析
**** Hidden Message *****

最佳战士排行榜

|第一名|第二名|第三名
名字|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. 因为额度原因，部分鱼油可能下一天才能奖励。

static/image/hrline/1.gif

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

创作不易，如果你喜欢，别忘了评分、顶{:10_281:}


本关满意度调查

zhangjinxuan 发表于 2023-3-20 19:15:59

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

sfqxx 发表于 2023-3-20 19:21:06

看看

高山 发表于 2023-3-20 19:29:28

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

zhangjinxuan 发表于 2023-3-20 19:31:23

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

你告诉我一个 求排列 的题目怎么编{:10_291:}

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

元豪 发表于 2023-3-20 19:36:52

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

元豪 发表于 2023-3-20 19:37:29

可以搞个样例解释{:10_256:}{:10_256:}

zhangjinxuan 发表于 2023-3-20 19:38:11

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

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

高山 发表于 2023-3-20 19:42:01

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

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

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

zhangjinxuan 发表于 2023-3-20 19:43:24

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

有道理{:10_256:}{:10_256:}{:10_256:}

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

元豪 发表于 2023-3-20 19:44:26

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

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

神奇!{:10_257:}

高山 发表于 2023-3-20 19:44:57

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

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

嗯嗯

额外减小 发表于 2023-3-21 06:20:02

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

sfqxx 发表于 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 > a:
            pos = i
            break
    else:
      return False
    for i in range(n - 1, pos, -1):
      if a > a:
            a, a = a, a
            break
    l = pos + 1
    r = n - 1
    while l <= r:
      a, a = a, a
      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 发表于 2023-3-21 18:45:59

本帖最后由 jhq999 于 2023-3-21 18:49 编辑

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

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

jhq999 发表于 2023-3-21 18:52:25

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

zhangjinxuan 发表于 2023-3-22 07:22:48

本帖最后由 zhangjinxuan 于 2023-3-22 07:25 编辑

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


？？？哪里

jhq999 发表于 2023-3-22 08:31:21

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 发表于 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 这个数据???
页: [1]
查看完整版本: 【C++板块提升计划】梦想护卫舰 第29期 排列 & 鱼CR1 B题题解【原创】