TOJ 2452 Ultra-QuickSort

描述

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.

输入

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

题目来源

Waterloo Feb.5 2005

 

求最小的交换次数,即求逆序对数问题,并归排序。

 

【并归排序】

如下演示并归排序的整个过程:

并归排序主要是深搜实现的。

{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;
}

TOJ 2452 Ultra-QuickSort

上一篇:Remove Duplicates from Sorted Array


下一篇:教你爱上Blocks(闭包)