解题思路:
注意事项:
参考代码:
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语言代码)浏览:1413 |
printf基础练习2 (C语言代码)浏览:305 |
WU-陶陶摘苹果2 (C++代码)浏览:975 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:641 |
哥德巴赫曾猜测 (C语言代码)浏览:2349 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:616 |
DNA (C语言描述,蓝桥杯)浏览:1555 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:676 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1072 |
大家好,我是验题君浏览:577 |