Ultra-QuickSort

Time Limit: 7000MS Memory Limit: 65536K Total Submissions: 59356 Accepted: 21972 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

题目链接：http://poj.org/problem?id=2299

题意

给个数组，求逆序对的个数。

题解

求逆序对的个数是快速排序的一个应用，在快排过程中，当右半边的数组复 制到t数组中时，左半边剩下的元素个数m-p就是当前逆序对的个数,每次排 序加上这个m-p就是结果。

---

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #include <stack> #include <queue> #include <vector> #define INF 0xffffffff using namespace std; const int maxn = 500000+5; int a[maxn]; int t[maxn]; void merge_sort(int x, int y, long long int & ans){ if(y-x>1){ int m = x+(y-x)/2; int p=x, q=m, i=x; merge_sort(x, m, ans); merge_sort(m ,y, ans); while(p<m || q<y){ if(q>=y || p<m && a[p]<=a[q]){ t[i++] = a[p++]; } else{ t[i++] = a[q++]; ans += m-p; } } for(int j=x; j<y; j++){ a[j] = t[j]; } } } int main(){ int n; while(scanf("%d", &n) == 1 && n){ for(int i=0; i<n; i++){ scanf("%d", &a[i]); } long long int ans = 0; merge_sort(0, n, ans); printf("%lld\n", ans); } return 0; }