首页 > 试题广场 >

逆序对距离之和

[编程题]逆序对距离之和
  • 热度指数:2593 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小易给定一个的排列,希望你能求出这个序列中所有逆序对的距离和。
下标的距离为,逆序对是指序列中一对下标满足 .

输入描述:
第一行数字表示排列长度 
接下来一行个数字表示这个排列



输出描述:
一行一个数字表示答案
示例1

输入

5  
1 3 4 2 5

输出

3

说明

逆序对:
(3, 2)距离为2
(4, 2)距离为1
总和为3
n = int(input())
nums = list(map(int, input().split()))
ans = 0
def mergesort(l):
    global ans
    L = len(l)

    if L <= 1:
        return l

    mid = L // 2
    left = mergesort(l[0:mid])
    right = mergesort(l[mid:])
    res = []
    
    sum_left = sum(left) if left else 0
    while left and right:
        if right[0] < left[0]:
            ans += sum_left - len(left) * right[0]
            res.append(right[0])
            right.pop(0)
        else:
            sum_left -= left[0]
            res.append(left[0])
            left.pop(0)
    if left:
        res += left
    elif right:
        res += right

    return res

mergesort(nums)

print(ans)
归并排序的同时记录和
发表于 2020-04-05 23:09:09 回复(10)