07622: 求排列的逆序数

http://cs101.openjudge.cn/practice/07622/

在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列 $i_{1} ， i_{2} ， \dots ， i_{n}$ ，如果其中存在j,k，满足 j < k 且 $i_{j} > i_{k}$ ，那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

输入

第一行是一个整数n，表示该排列有n个数（n <= 100000)。第二行是n个不同的正整数，之间以空格隔开，表示该排列。

输出

输出该排列的逆序数。

样例输入

6
2 6 3 4 5 1

样例输出

提示

利用二分归并排序算法（分治）；
注意结果可能超过int的范围，需要用long long存储。

来源

习题(15-4)

python

mininum=0
def mergesort(arr):
    global mininum
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        mergesort(left)
        mergesort(right)

        Lptr = Rptr = ptr = 0
        while len(left) > Lptr and len(right) > Rptr:
            if left[Lptr] <= right[Rptr]:
                arr[ptr] = left[Lptr]
                Lptr += 1
            else:
                arr[ptr] = right[Rptr]
                Rptr += 1
                mininum += len(left) - Lptr
            ptr += 1

        while len(left) > Lptr:
            arr[ptr] = left[Lptr]
            ptr += 1
            Lptr += 1
        while len(right) > Rptr:
            arr[ptr] = right[Rptr]
            ptr += 1
            Rptr += 1


n = int(input())
arr = list(map(int, input().split()))
mergesort(arr)
print(mininum)

挺巧方法，就是insert是O(n)，慢了。1254ms

python

from bisect import bisect_left

n = int(input())
lst = list(map(int, input().split()))
dp = []
res = 0

for i in range(n - 1, -1, -1):
    p = bisect_left(dp, lst[i])
    res += p
    dp.insert(p, lst[i])

print(res)

尹显齐25物院：当时基本上没学过算法，看着提示里的“二分归并排序算法”也不知道在说什么，然后自己想了一个新方法，代码好像还短很多，当时想到兴奋了一整个晚上。

思路：考虑前 $i - 1$ 个数组成的有序数列，此时处理第 $i$ 个数，我们为了找到这个新增的数所添加的逆序数对数，只需要计算比它大的数有多少就可以。同时我们还要继续维护数列的有序，使这种方法能对 $i + 1$ 个数使用。此时我们发现，二分插入可以同时做到这两点，这就是巧妙之处。此方法时间复杂度同样为为 $O (n \log n)$ 。

代码

python

import bisect
n = int(input())
nums = list(map(int,input().split()))
n1 = [nums[0]]
a = 0
for i in nums[1:]:
	index = bisect.bisect(n1,i)
	n1.insert(index,i)
	a += len(n1) - index - 1
print(a)

07622: 求排列的逆序数 ​

07622: 求排列的逆序数