原题链接：2396 - 求排列的逆序数-东方博宜OJ
题目描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。
考虑1,2,…,n 的排列 A1，A2，…，An，如果其中存在j,k，满足 j < k 且 Aj > Ak， 那么就称(Aj , Ak)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 2 6 3 4 5 1 含有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
输出
8
来源
电子学会等级考试五级样题
标签
分治电子学会等级考试
题目分析
题目要求计算一个排列的逆序数。逆序数的定义是：在一个排列中，如果存在两个数 Aj 和 Ak，满足j<k 且 Aj>Ak，那么(Aj,Ak) 就是一个逆序对。逆序数就是所有逆序对的数量。
解题思路
-
归并排序：本题的核心算法是利用归并排序的思想来计算逆序数。归并排序是一种分治算法，它将数组分成两部分，分别排序后再合并。在合并的过程中，可以顺便计算逆序数。
-
逆序数的计算：在归并排序的合并阶段，如果左半部分的某个元素大于右半部分的某个元素，那么左半部分剩余的所有元素都大于右半部分的当前元素，因此可以一次性计算出多个逆序对。
代码实现
-
Merge函数：在归并排序的合并过程中，计算逆序数。具体步骤如下：
-
使用两个指针 p1 和 p2 分别指向左半部分和右半部分的当前元素。
-
如果 a[p1] < a[p2]，则将 a[p1] 放入临时数组 tmp 中。
-
如果 a[p1] > a[p2]，则将 a[p2] 放入临时数组 tmp 中，并计算逆序数 sum += m - p1 + 1，表示左半部分剩余的元素都大于 a[p2]。
-
MergeSort函数：递归地将数组分成两部分，分别排序后再合并。
-
主函数：读取输入数据，调用 MergeSort 函数进行排序并计算逆序数，最后输出结果。
代码解释
#include<bits/stdc++.h>
using namespace std;
long long sum;//记录逆序数个数
void Merge(long long a[], int s, long long m, int e, long long tmp[]) { int pb=0; int p1=s,p2=m+1; int count=e-p2+1; while(p1<=m&&p2<=e){ if(a[p1]<a[p2])tmp[pb++]=a[p1++];//归并时小的先进tmp else{ tmp[pb++]=a[p2++]; sum+=m-p1+1;//计算逆序数 } } while(p1<=m){ tmp[pb++]=a[p1++]; } while(p2<=e){ tmp[pb++]=a[p2++]; } for(int i=0;i<e-s+1;++i){ a[s+i]=tmp[i]; }
}
void MergeSort(long long a[], long long s, int e, long long tmp[]) { if(s<e){ int m=s+(e-s)/2; MergeSort(a,s,m,tmp); MergeSort(a,m+1,e,tmp); Merge(a,s,m,e,tmp); }
}
long long n,a[100010],b[100010];
int main(){cin>>n; for(int i=0;i<n;i++){ cin >> a[i]; } MergeSort(a,0,n-1,b); cout<<sum; return 0;
}
总结
通过归并排序的思想，我们可以在 O(nlogn) 的时间复杂度内计算出排列的逆序数。这种方法充分利用了归并排序的特性，在合并过程中高效地计算逆序对的数量。
制作不易，点个赞吧┭┮﹏┭┮
