Description
对于数列a1,a2,a3…中的任意两个数ai,aj (i < j)，如果ai > aj,那么我们就说这两个数构成了一个逆序对；在一个数列中逆序对的总数称之为逆序数，如数列 1 6 3 7 2 4 9中，(6,4)是一个逆序对，同样还有(3,2),(7,4),(6,2)，(6,3)等等，你的任务是对给定的数列求出数列的逆序数。
Input
输入数据N(N <= 100000)表示数列中元素的个数，随后输入N个正整数，数字间以空格间隔。
Output
输出逆序数。
Sample Input
10
109 8 7 6 5 4 3 2 1
Sample Output
45
参考程序
#include <stdio.h>
#define LEN 100000
long long int MergeCountSkip(int a[],int low,int mid,int high)
{
//在归并排序的过程中，顺便统计分别位于左右两个数组的，具备逆序关系的元素对
int buffer[high+5],i;
long long int Skip=0;
for(i=low;i<=high;i++)
{
buffer[i]=a[i];
}
int p1=low,p2=mid+1,k=0;
while(p1<=mid && p2<=high)
{
if(buffer[p1]<=buffer[p2])
{
a[low+k]=buffer[p1];
k++;
p1++;
}
else
{
a[low+k]=buffer[p2];
Skip=Skip+(mid-p1+1);
//出现跨数组的逆序:与buffer[p2]构成逆序关系的数是来自数组左侧的一部分， buffer[p1]~buffer[mid]
k++;
p2++;
}
}
if(p1<=mid)
{
while(p1<=mid)
{
a[low+k]=buffer[p1];
k++;
p1++;
}
}
else
{
while(p2<=high)
{
a[low+k]=buffer[p2];
k++;
p2++;
}
}
return Skip;
}
long long int MergeSort_Count(int a[],int low,int high)
{
long long int LeftCount,RightCount,SkipCount;
if(low>=high)
{
return 0;//仅一个数据，逆序数为0
}
else
{
int mid=(low+high)/2;
LeftCount=MergeSort_Count(a,low,mid);
RightCount=MergeSort_Count(a,mid+1,high);
SkipCount=MergeCountSkip(a,low,mid,high);
return LeftCount+RightCount+SkipCount;
}
}
int main()
{
int a[LEN+5],n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
long long int sum=MergeSort_Count(a,0,n-1);
printf("%lld\n",sum);
return 0;
}
分析
本题的思路利用分治的方法，将数组一分为二，那么原数组的逆序数=左侧数组的逆序数LeftCount+右侧数组的逆序数RightCount+跨数组逆序数SkipCount（解释：一个元素来自左侧，另一个元素来自右侧，二者构成逆序关系，因此此种情况也要考虑在内）。考虑到归并排序的步骤是将问题分解，然后在递归合并子问题，这一思想与本题非常一致。也别是在合并过程中，有序顺序表的归并过程就包含了元素比较，利用这一机会恰好可以统计上述SkipCount。此外还需注意，只有一个元素本身，它的逆序数就是0.这样算法的时间复杂度与归并排序的O(nlogn)一致。
在提交时，要注意数据规模，n=100000，我们知道一串数的逆序数最多可达到n(n-1)/2，超过整型int的范围，因而要特别小心变量的类型、函数的返回值类型。
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: