赞
踩
思路如下:
① 优先考虑特殊情况,数组是一个严格递减的数组(每个数字之间相差1,最后一位必须为1),例子如下: 长度为 7 ,对应的数组为 [7,6,5,4,3,2,1],根据组合数学 C(7 , 2) = 21,共有21对逆序对 长度为 8 ,对应的数组为 [8,7,6,5,4,3,2,1],根据组合数学 C(8 , 2) = 28,共有28对逆序对 假设逆序对个数为 x 时,当 x ∈ (21,28] ,其数组长度为 8;当 x = 21 时,数组长度为 7 ② 那么如果 C(L , 2) 不等于 x 呢,假如 x = 25,通过第①步可以求得 L = 7,数组为 [7,6,5,4,3,2,1] ,共 21 对逆序对,那么差4对怎么补齐?其实只要在数组开头添加一个 5 即可,数组变为 [5,7,6,5,4,3,2,1],多了第一个5和黄色的数字组成的逆序对,刚好4对 当然这个只是其中一个答案,不符合字典序最小的要求。因此需要化简: 一、 [5,7,6,5,4,3,2,1] 把5改成4 得到 [5,7,6,4,4,3,2,1] ,可以发现逆序对的个数是没有变化的,那是因为原来加粗了的逆序对,改变成了修改后加粗的逆序对,也仅有这一对发生了转移,因此逆序对个数没变,但是字典序变小了。 二、 [5,7,6,4,4,3,2,1] 贪心,把黄色部分都减1 得到 [5,6,5,4,4,3,2,1],很明显逆序对个数依然没有改变,但是字典序变小了。 三、[5,6,5,4,4,3,2,1] 黄色部分改成 [5,6,5,4,3,2,1,1] ,相当于把 4 变成 1 ,可以发现逆序对个数依然没有改变,但是字典序变小了。 四、[5,6,5,4,3,2,1,1] 这情况又和第一步很相似了,把5改成4 得到 [5,6,4,4,3,2,1,1],一直重复步骤一至步骤三,可以得到最终结果: [5,4,3,3,2,2,1,1] 这个结果就是最"简化"了的,也就是字典序最小 ③ 找规律 x ∈ (21,28] ,结果如下:
根据标黄和标红的部分可以发现有很明显的规律,就像两个三角形,或者阶梯更恰当。
黄色阶梯没有标黄的部分,规律都是严格递减的
红色阶梯没有标红的部分,除了开头那个数字,规律都是严格递减的,而开头的数字跟加粗的数字是相等的
1、应为n+1长度
2、最终序列可看成是三递减序列的组合:数字a、a-1递减序列和b递减序列。且a+b==n+1。
3、三个序列的组合规律是:先把a-1序列和b递减序列组合,然后降序排序,然后把a插入到头部。
python代码
import sys from collections import Counter from heapq import * input = lambda: sys.stdin.readline().strip() x = int(input()) if x == 0 : print(1) else : def get(x) : return x * (x - 1) // 2 i = 2 while get(i) < x : i += 1 ans = [] n = i n -= 1 a = x - get(n) + 1 b = n + 1 - a for i in range(1 , a) : ans.append(i) for i in range(1 , b + 1) : ans.append(i) ans.sort(reverse=True) ans.insert(0 , a) print(n + 1) for x in ans : print(x , end = ' ')
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。