首页 > 代码库 > ZJNU 1247 归并排序求逆序对

ZJNU 1247 归并排序求逆序对

2024-07-11 09:37:59   214人阅读

逆序对——高级


Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 118 Accepted: 28

Description

对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。 

　　例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。 

求n个数中的逆序对个数。 

Input

第一行一个整数n(<=1,000,000) 

第二行n个整数，a[i]<=2^31-1 
 

Output

n个数中逆序对个数
 

Sample Input

5
3 1 4 5 2
 
 

Sample Output

4
 
 
由于数组太大，所以本题采用归并排序求逆序对。归并排序就是采用分治的思想把数组分成两份，然后两份排序，用两份排好序的数组合并，使最终数组排序。
由于每次对一个数组排序的时候，该数组的两个子数组已排好序（假设是升序排列），设两个子数组分别为b[i], c[j]（b数组是母数组前半部分）母数组为a[k]。合并的代码如下：
 
if(b[i]<=c[j]) a[k++]=b[i++];
else a[k++]=c[j++];
 
易知若b[i]>c[j],则 b数组中 i 后面的都大于c[j]，设b数组范围为[left,mid],那么在c数组j位置可以构成mid-i+1个逆序数，这样c数组每个元素所构成的逆序数相加即为a数组中的逆序数总数。所以可以在归并排序的过程中算出总逆序数，时间复杂度即为归并排序的时间复杂度nlogn。
 
代码即为归并排序的代码，只是加了一些求逆序对数的代码：
 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5  6  7 int a[1000005]; 8 int b[1000005]; 9 __int64 ans;10 11 void bing(int left,int mid,int right)12 {13     int i, j, k;14     for(i=left;i<=right;i++)15     b[i]=a[i];16     i=left;j=mid+1;k=left;17     while(i<=mid&&j<=right)18     {19         if(b[i]<=b[j]) a[k++]=b[i++];20         else{21             a[k++]=b[j++];22             ans+=mid-i+1;23         }24     }25     while(i<=mid) a[k++]=b[i++];26     while(j<=right) a[k++]=b[j++];27 }28 29 void msort(int left,int right)30 {31     if(left<right)32     {33         34         int mid=(left+right)/2;35         msort(left,mid);36         msort(mid+1,right);37         bing(left,mid,right);38     }39 }40 main()41 {42     int n, i;43     scanf("%d",&n);44     for(i=1;i<=n;i++) scanf("%d",&a[i]);45     ans=0;46     msort(1,n);47     printf("%I64d\n",ans);48 }

 


联系
我们