464
归并求逆序对【模板】
代码：
#include <stdio.h>
const int M=999999;
int A[500];
int cunt=0;
int L[250],R[250];
void Merge(int Left,int Middle,int Right)
{
int n1=Middle-Left+1;
int n2=Right-Middle;
for(int i=1;i<=n1;i++)
L[i]=A[Left+i-1];
for(i=1;i<=n2;i++)
R[i]=A[Middle+i];
L[n1+1]=M;
R[n2+1]=M;
i=1;
int j=1;
for(int k=Left;k<=Right;k++)
{
if(L[i]<=R[j])
A[k]=L[i++];
else
{
A[k]=R[j++];
cunt+=n1-i+1; //cunt为全局变量
}
}
}
void Merge_sort(int Left,int Right)
{
int Middle;
if(Left<Right)
{
Middle=(Left+Right)/2;
Merge_sort(Left,Middle); // 二分分解左部分
Merge_sort(Middle+1,Right); // 二分分解有部分
Merge(Left,Middle,Right); //合并两部分
}
}
int main()
{
int n;
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%d",&A[i]);
Merge_sort(1,n);
printf("%d\n",cunt);
return 0;
}
运行结果：
5
2 3 8 6 1
5
最后更新：2017-04-03 14:54:11