归并-求逆序数

考虑1,2,…,n (n <= 100000)的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。 
 
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个 逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆 序数就是8。 
 
现给定1,2,…,n的一个排列，求它的逆序数

分治（归并）做到O(nlogn)： 
 
 
1） 将数组分成两半，分别求出左半边的逆序数和右半边的逆序数 
2） 再算有多少逆序是由左半边取一个数和右半边取一个数构成(要求O(n)实 现） 

2的关键：左半边和右半边都是排好序的。比如，都是从大到小排序的。这 样，左右半边只需要从头到尾各扫一遍，就可以找出由两边各取一个数构成的 逆序个数 

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int N = 1005;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int a[N],tmp[N];
     
    
   

    

     

    
    

     

      int ans;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Merge(int l,int m,int r)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i = l;
     
    
   

    

     

    
    

     
 int j = m + 1;
     
    
   

    

     

    
    

     
 int k = l;
     
    
   

    

     

    
    

     
 while(i <= m && j <= r)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(a[i] > a[j]){
     
    
   

    

     

    
    

     

       tmp[k++] = a[j++];
     
    
   

    

     

    
    

     

       ans += m - i + 1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else tmp[k++] = a[i++];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 while(i <= m) tmp[k++] = a[i++];
     
    
   

    

     

    
    

     
 while(j <= r) tmp[k++] = a[j++];
     
    
   

    

     

    
    

     
 for(int i=l;i<=r;i++)
     
    
   

    

     

    
    

     

       a[i] = tmp[i];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Merge_sort(int l,int r)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(l < r)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int m = (l + r) >> 1;
     
    
   

    

     

    
    

     

       Merge_sort(l,m);
     
    
   

    

     

    
    

     

       Merge_sort(m+1,r);
     
    
   

    

     

    
    

     

       Merge(l,m,r);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int n,T,tt=1;
     
    
   

    

     

    
    

     
 scanf("%d",&T);
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&n);
     
    
   

    

     

    
    

     
 for(int i=0;i<n;i++)
     
    
   

    

     

    
    

     
 scanf("%d",&a[i]);
     
    
   

    

     

    
    

     

       ans = 0;
     
    
   

    

     

    
    

     

       Merge_sort(0,n-1);
     
    
   

    

     

    
    

     
 printf("Scenario #%d:\n%d\n\n",tt++,ans);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/81773190