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 0Sample Output
6 0//归并排序模板，只加了一句 cnt += m-p;
1 #include<stdio.h> 2 #include<string.h> 3 long long cnt; 4 int num[500010],tmp[500010]; 5 void merge_sort(int num[],int x, int y, int tmp[]) 6 { 7 if(y-x > 1) 8 { 9 int m = x + (y-x)/2; 10 int p = x, q = m, i = x; 11 merge_sort(num,x,m,tmp); 12 merge_sort(num,m,y,tmp); 13 while(p < m || q < y) 14 { 15 if(q >= y || (p < m && num[p] <= num[q])) 16 tmp[i++] = num[p++]; 17 else 18 { 19 tmp[i++] = num[q++]; 20 cnt += m-p; 21 } 22 } 23 for(i = x; i < y; i++) 24 num[i] = tmp[i]; 25 } 26 } 27 int main() 28 { 29 int n; 30 while(~scanf("%d",&n) && n) 31 { 32 for(int i = 0; i < n; i++) 33 scanf("%d",&num[i]); 34 cnt = 0; 35 merge_sort(num,0,n,tmp); 36 printf("%I64d\n",cnt); 37 } 38 return 0; 39 } View Code
转载于:https://www.cnblogs.com/LK1994/p/3254388.html
相关资源：JAVA上百实例源码以及开源项目