解题思路:
注意事项:
参考代码:
def mergeSort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = mergeSort(arr[:mid])
right, right_inv = mergeSort(arr[mid:])
merged, merge_inv = merge(left, right)
return merged, left_inv + right_inv + merge_inv
def merge(left, right):
merged = []
inversions = 0
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
inversions += len(left) - i
j += 1
while i < len(left):
merged.append(left[i])
i += 1
while j < len(right):
merged.append(right[j])
j += 1
return merged, inversions
n = int(input())
arr = list(map(int, input().split()))
_, inversions = mergeSort(arr)
print(inversions)
0.0分
1 人评分
三进制小数 (C语言代码)浏览:1019 |
点我有惊喜!你懂得!浏览:1514 |
点我有惊喜!你懂得!浏览:1234 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:2468 |
数列 (C++代码)浏览:664 |
C语言训练-自由落体问题 (C语言代码)浏览:1733 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:667 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:520 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:629 |
第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略浏览:1145 |