给定一个正整数 x,请找出一个尽可能短的仅含正整数的数组 A 使得 A 中 恰好有 x 对 i, j 满足 Ai > Aj 。 如果存在多个这样的数组,请输出字典序最小的那个。python
时间: 2024-05-22 07:14:01 浏览: 98
题目有点棘手,让我先回答一下。给定一个正整数x,可以考虑构造数组A=[1,2,3,...,x],那么A中任意两数组成的数对中,Ai>Aj的数对数量为C(x,2)=x(x-1)/2,即x个数字的所有数对中,恰好有x(x-1)/2个数对满足Ai>Aj。因此,数组A是一个最短的符合条件的数组,字典序也是最小的。
阅读全文