2725531_ac_15ms_112k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 64 行

#include <stdio.h>
#include <string.h>

int a[1001], b[1001];
int res;

void merge(int p, int q, int r)
{
        int i, j = 0;
        int beginA = p, endA = q, beginB = q+1, endB = r;
        
        while(beginA <= endA && beginB <= endB) {
                if(a[beginA] <= a[beginB]) {
                        b[j++] = a[beginA++];
                } else {
                        b[j++] = a[beginB++];
                        res += q - beginA + 1;
                }
        }
        while(beginA <= endA) {
                b[j++] = a[beginA++];
        }
        while(beginB <= endB) {
                b[j++] = a[beginB++];
        }
        for(i = 0; i < j; i++) {
                a[p+i] = b[i];
        }
}

void msort(int first, int last)
{
        if(first < last) {
                int mid = (first + last) / 2;
                msort(first, mid);
                msort(mid+1, last);
                merge(first, mid, last);
        }
}



void input()
{
    int i, n;

    scanf("%d",&n);
    for (i = 0; i < n; i++)
        scanf("%d",&a[i]);
    res = 0;
    msort(0,n-1);
    printf("%d\n\n",res);
}

int main()
{
	int t, cas = 1;

	scanf("%d",&t);
    while(t--)
		printf("Scenario #%d:\n",cas++),input();
    return 0;
}