-
在Internet上的搜索引擎经常需要对信息進行比较比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,从而实现个性化的服务
对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1i2,…in,如果其中存在j,k满足 j < k 且 ij > ik, 那么就称(ij,ik)是这个排列的一个逆序
构成的所有n!个排列中,最小的逆序数是0对应的排列就是1,2,…,n;最大的逆序数是n(n-1)/2,对应的排列就是n,(n-1),…,2,1逆序数越大的排列与原始排列的差异度就越大。
现給定1,2,…,n的一个排列求它的逆序数。
-
第一行是一个整数n表示该排列有n个数(n <= 100000)。
第二行是n个不同的正整数之间以空格隔开,表示该排列 -
用了归并排序,在最后的排序过程中巧妙地的利用分治和其已有的排序顺序,求出逆序对数