poj 2299 -- Ultra-QuickSort

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 39538		Accepted: 14259

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

Sample Output

6
0

水题，与归并排序求逆序对是一个道理。

 1 /*======================================================================
 2  *           Author :   kevin
 3  *         Filename :   Ultra-QuickSort.cpp
 4  *       Creat time :   2014-07-14 10:10
 5  *      Description :
 6 ========================================================================*/
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <cstdio>
10 #include <cstring>
11 #include <queue>
12 #include <cmath>
13 #define clr(a,b) memset(a,b,sizeof(a))
14 #define M 500005
15 using namespace std;
16 long long s[M],temp[M],cnt;
17 void mergearray(long long a[],int first,int mid,int last,long long temp[]){
18     int i = first,j = mid + 1;
19     int m = mid,  n = last;
20     int k = 0;
21     while(i <= m && j <= n){
22         if(a[i] < a[j])
23             temp[k++] = a[i++];
24         else{
25             temp[k++] = a[j++];
26             cnt += mid-i+1;
27         }
28     }
29     while(i <= m)
30         temp[k++] = a[i++];
31     while(j <= n)
32         temp[k++] = a[j++];
33     for(i = 0; i < k; i++)
34         a[first+i] = temp[i];
35 }
36 void mergesort(long long a[],int first,int last,long long temp[])
37 {
38     if(first < last){
39         int mid = (first + last) / 2;
40         mergesort(a,first,mid,temp);
41         mergesort(a,mid+1,last,temp);
42         mergearray(a,first,mid,last,temp);
43     }
44 }
45 int main(int argc,char *argv[])
46 {
47     int n;
48     while(scanf("%d",&n)!=EOF && n){
49         cnt = 0;
50         for(int i = 0; i < n; i++){
51             scanf("%lld",&s[i]);
52         }
53         mergesort(s,0,n-1,temp);
54         printf("%lld
",cnt);
55     }
56     return 0;
57 }

View Code

Do one thing , and do it well !