题目描述
给定一个数组 $a_1,a_2,…,a_n$。
如果数组$a$满足对于任意 $1≤i<j≤n$,$j − a_j ≠ i − a_i$ 均成立,则称数组$a$是一个好数组。
现在,请你通过将数组$a$中的元素任意重新排序来使其变为一个好数组(当然,你也可以选择保留初始顺序)。
可以通过数组重排得到的好数组可能不止一个,你只需输出任意一个满足条件的即可。
例如,对于数组 [1,1,3,5],重排后的好数组有 [1,3,5,1],[3,5,1,1],[5,3,1,1] 等等,而不好的数组有 [3,1,5,1],[1,1,3,5],[1,1,5,3] 等等。
样例
输入样例
3
1
7
4
1 1 3 5
6
3 2 1 5 6 4
输出样例
7
1 5 1 3
2 4 6 1 3 5
算法
数学推导
根据题目描述,数组$a$为好数组的条件为:
$1≤i<j≤n$
$j − a_j ≠ i − a_i$
根据以上条件可得:
$j-i ≠ a_j - a_i$, $j > i$, $j-i > 0$
因此,等号成立的可能条件为: $a_j - a_i > 0$
综上所述,满足不等号成立的条件可以转化为: $a_i - a_j > 0$,即将数组按照从大到小进行排序即可满足条件。
python3代码
def partition(left, right, li):
tmp = li[left]
while left < right:
while left < right and li[right] <= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] >= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
def Quick_Sort(left, right, li): #简单的快速排序
if left < right:
mid = partition(left, right, li)
Quick_Sort(left, mid-1, li)
Quick_Sort(mid+1, right, li)
def main():
T = int(input())
for _ in range(T):
n = int(input())
arr = list(map(int, input().rstrip().split(' ')))
Quick_Sort(0, len(arr)-1, arr)
print(' '.join(map(str, arr)))
if __name__ == '__main__':
main()
时间复杂度
$O(nlogn)$