Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 44489 | Accepted: 16176 |
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 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
59105431230
Sample Output
60 题目大意就是让你计算一个冒泡排序中，需要交换的次数。 以为数据量较大，所以我们这里用到了Merge Sort :
1 #include2 #include 3 int temp[500005] ; 4 int a[500005] ; 5 __int64 number ; 6 void MergeSort( int a[] , int fir , int end ) 7 { 8 int len = end - fir ; 9 if( len <= 1 )10 return ;11 int mid = fir + len/2 ;12 MergeSort( a , fir , mid ) ;13 MergeSort( a , mid , end ) ;14 int p1 = fir , p2 = mid ;15 for( int i = fir ; i < end ; i++ )16 {17 if( p1 == mid )18 {19 temp[i] = a[p2++] ;20 }21 else if( p2 == end )22 {23 temp[i] = a[p1++] ;24 }25 else26 {27 if( a[p1] >= a[p2] )28 {29 temp[i] = a[p2++] ;30 number += mid - p1 ;//在Merge Sort 排序中仅仅多加了这句话31 }32 else33 {34 temp[i] = a[p1++] ;35 }36 }37 }38 39 for(int i = fir ; i < end ; i++ )40 {41 a[i] = temp[i] ;42 }43 }44 int main()45 {46 // freopen("a.txt" ,"r" , stdin );47 int n ;48 while( scanf("%d" , &n ) != EOF )49 {50 if( n == 0 ) break;51 number = 0 ;52 for(int i = 0 ; i < n ; i++ )53 scanf("%d" , &a[i] ) ;54 MergeSort( a , 0 , n ) ;55 56 printf("%I64d\n" , number );57 }58 return 0 ;59 }