By yusijia

Updated:

Contents
  1. 1. 分析

分析

　　归并排序是将数列a[left, right]分成两半a[left,mid]和a[mid+1,right]分别进行归并排序，然后再将这两半合并起来。
在合并的过程中（设left<=i<=mid，mid+1<=j<=right），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在
temp数组前半部分[left,mid]中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并
排序中的合并过程中计算逆序数.

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
#include<stdio.h>

const int N = 1005;

int a[N], b[N];
int ans;

void mergearray(int a[], int first, int mid, int last, int temp[])//temp数组用于临时储存另外一组数
{
    int i = first, j = mid + 1;
    int k = 0;
    while(i <= mid && j <= last) 
    {
        if(a[i] <= a[j]){
            temp[k++] = a[i++];  
        }else{
            temp[k++] = a[j++]; 
            ans += mid - i + 1;
        }
    }
    while(i <= mid)
        temp[k++] = a[i++];     
    while(j <= last)
        temp[k++] = a[j++];    
    for(i = 0; i < k; i++)
        a[first + i] = temp[i];
}

void mergesort(int a[], int first, int last, int temp[])
{
    if(first < last)  
    {
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp); 
        mergesort(a, mid + 1, last, temp); 
        mergearray(a, first, mid, last, temp);
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    int n, T, tt = 1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        ans = 0;
        mergesort(a, 0, n-1, b);
        printf("Scenario #%d:\n%d\n\n", tt++, ans);
    }
    return 0;
}
Contents
  1. 1. 分析