解题思路:
首先题目描述有问题，没有说明 i 和 j 的关系，应该是保证 i < j 时使 Ai > Aj (简称逆序对) ，我不太理解，这可是比赛，描述竟然能如此含糊，爷想笑，水份杯果然名不虚传。
思路如下：
① 优先考虑特殊情况，数组是一个严格递减的数组（每个数字之间相差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
如何去求数组长度呢？假设 数组 长度为 L ，C(L , 2) ≥ x，可以二分长度，也可以直接解方程，简简单单二元一次方程，初中知识：
L * (L-1) / 2 ≥ x
=> L2 - L - 2x ≥ 0
然后套求根公式，求出正根即可，当 C(L , 2) 刚好等于 x，那答案就是一个严格递减的数组 （每个数字之间相差1，最后一位必须为1）
② 那么如果 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] ，结果如下：
| 22 | 26543211 |
| 23 | 35432211 |
| 24 | 44332211 |
| 25 | 54332211 |
| 26 | 65432211 |
| 27 | 76543211 |
| 28 | 87654321 |
根据标黄和标红的部分可以发现有很明显的规律，就像两个三角形，或者阶梯更恰当。
黄色阶梯没有标黄的部分，规律都是严格递减的
红色阶梯没有标红的部分，除了开头那个数字，规律都是严格递减的，而开头的数字跟加粗的数字是相等的
有这些规律就足够得出结果了。
参考代码 （python）:
n = int(input()) # x*(x-1)/2 >= n # x2 - x - 2*n >= 0 # 求根公式获取结果数组长度 x = int((1 + (1+8*n)**0.5) / 2) if x*(x-1) == 2 * n: print(x) print(x,end='') x -= 1 while x: print(' ',end='') print(x,end='') x -= 1 else: x += 1 print(x) total = x*(x-1)//2 # 倒数第total个 total -= n from collections import deque
res = deque()
# 黄色阶梯部分 if total <= x // 2: num = 1 while num <= total: res.append(num) res.append(num) num += 1 while len(res) < x: res.append(num) num += 1 # 红色阶梯部分 else: tmp = x - total - 1 num = 1 while num <= tmp: res.append(num) res.append(num) num += 1 tmp = num while len(res) < x - 1: res.append(num) num += 1 res.append(tmp)
print(res.pop(),end='') while res: print(' ',end='') print(res.pop(),end='') print() |
0.0分
5 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复