本文共 1918 字，大约阅读时间需要 6 分钟。

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,

Ultra-QuickSort produces the output

0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5

9 1 0 5 4 3 1 2 3 0 Sample Output

6

0

题意是求归并排序时，至少要交换几次相邻的数字。

别人都说是求逆序对，规模这么大肯定不能暴力，这里还有个性质，要模拟一下归并排序，在归并排序的合并操作里，对于数列[l, mid] [mid + 1, r]的合并，i 从l开始循环，j从mid + 1开始循环，如果遇到a[i] > a[j] 则出现逆序，可以将a[j]放入辅助数组，同时j++，那么和a[j]逆序的数就有mid-i+1个，因为序列是有序的[i, mid]的所有的数都是大于a[j]的[见]

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define INF 0x3f3f3f3f#define MAXN 500005#define Mod 10001using namespace std;long long a[MAXN],b[MAXN],ans;void copy(long long a[],int l,int r){ for(int i=l;i<=r;++i) a[i]=b[i];}void merge(long long a[],int l,int mid,int r){ int i=l,j=mid+1; int s=l; while(i<=mid&&j<=r) { if(a[i]
            
             >1; mergesort(a,l,m); mergesort(a,m+1,r); merge(a,l,m,r); copy(a,l,r); }}int main(){ int n; while(~scanf("%d",&n)&&n) { ans=0; for(int i=1; i<=n; ++i) scanf("%I64d\n",&a[i]); mergesort(a,1,n); printf("%I64d\n",ans); } return 0;}
            
           
          
         
        
       
      
     
    
   

转载地址：http://fxcvb.baihongyu.com/