描述
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
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.
输入
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.
输出
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.
样例输入
5
9
1
0
5
4
3
1
2
3
0
样例输出
6
0
题目来源
求最小的交换次数,即求逆序对数问题,并归排序。
【并归排序】
如下演示并归排序的整个过程:
并归排序主要是深搜实现的。
{9,1,0,4,5,8,7,4,3}=>{9,1,0,4,5} {8,7,4,3}
{9,1,0,4,5}=>{9,1,0} {4,5}=>{9}{1}{0} {4}{5}
{8,7,4,3}=>{8,7} {4,3}=>{8}{7} {4}{3}
合并子表
{0,1,9} {4,5} {7,8} {3,4}
{0,1,4,5,9} {3,4,7,8}
{0,1,3,4,4,7,8,9}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <stdio.h> __int64
sum;
void
mergeSort( int * a, int
low, int
mid, int
high){
int * p= new
int [high+1];
int
i=low;
int
j=low; //左侧表的起始位置
int
h=mid+1; //右侧表的起始位置
while (h<=high&&j<=mid){
if (a[j]<=a[h]){
p[i]=a[j];
j++;
i++;
} else {
//求逆序数
sum+=h-i;
p[i]=a[h];
h++;
i++;
}
}
for (;j<=mid;j++,i++){
p[i]=a[j];
}
for (;h<=high;h++,i++){
p[i]=a[h];
}
for (i=low;i<=high;i++){
a[i]=p[i];
}
delete [] p;
} void
merge( int * a, int
low, int
high){
if (low<high){
int
mid=(low+high)>>1;
//划分子表
merge(a,low,mid);
merge(a,mid+1,high);
//合并子表
mergeSort(a,low,mid,high);
}
} int
main()
{ int
n;
int
arr[500010];
while ( scanf ( "%d" ,&n)!=EOF && n){
for ( int
i=0; i<n; i++){
scanf ( "%d" ,&arr[i]);
}
sum=0;
merge(arr,0,n-1);
printf ( "%I64d\n" ,sum);
}
return
0;
} |