问题F:求逆序对（Python）
发布时间
阅读量：
阅读量
题目描述
对于一个由a1,a2,…,an组成的序列，若存在i<j且ai>aj的情况，则称这一对元素为逆序对，现要求计算该序列中逆序对的总数。
需要注意的是，n的取值范围不超过105，且每个元素ai的数值上限为105。
输入
第一行给出数值n，用于表示序列的长度。
随后的n行内容中，第i+1行对应的是序列中的第i个数值。
小标题
全部逆序对的总数量。
样例输入 Copy
4
3
2
3
2
样例输出 Copy
3
def reverseNumMerge(a,lt,rt):
if lt==rt:
return 0
mid = (lt+rt)//2
x1 = reverseNumMerge(a,lt,mid)
x2 = reverseNumMerge(a,mid+1,rt)
return x1+x2+merge(a,lt,mid,rt)
def merge(a,lt,mid,rt):
x = 0
tmp = [0]*(rt-lt+1)
i,j,k = lt,mid+1,0
while i<= mid and j<=rt:
if a[i] <=a[j]:全部评论 (0)
还没有任何评论哟~