Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 56263 | Accepted: 20773 |
Description
Ultra-QuickSort produces the output
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 5 4 3 1 2 3
Sample Output
6
Source
题解：
就是让你求逆序对数
#include<iostream>
#include<cstdio>
using namespace std;
long long cnt;
void merge_sort(int *A,int l,int r,int *T)
{
if(r-l>1)
{
int m = l + (r-l)/2;
int p = l,q = m,i = l;
merge_sort(A,l,m,T);
merge_sort(A,m,r,T);
while(p < m || q < r)
{
if(q>=r || (p<m && A[p]<=A[q]))
T[i++]=A[p++];
else
{
T[i++]=A[q++];
cnt += m - p;
}
}
for(int i = l;i < r;i ++)
A[i]=T[i];
}
}
int main()
{
int *A,*T;
int n;
while(scanf("%d", &n) != EOF)
{
if(n == 0)
return 0;
cnt = 0;
A = new int[n+1];
T = new int[n+1];
for(int i = 0;i < n;i ++)
scanf("%d", &A[i]);
merge_sort(A,0,n,T);
cout<<cnt<<endl;
}
return 0;
}