NYOJ117 求逆序数

题目分析：
如果直接一个一个的找，时间复杂度是O(n^2)，这道题数据量很大，这样肯定会超时的。我们肯定都之后把有序数组a和b归并成另外一个有序数组。这个思想可以用到这里来，假设需要归并的数据段是[Begin,Mid)和[Mid,End)。用i，j分别遍历两个数据段，如果后面数据段中有数据比前一个数据段中的元素小，那么它跨越的长度就是逆序对的个数，即Mid-i，i是第一个比j大的数。这里要注意，数组最大的元素个数是10^6，最多的逆序对的个数为10^12-10^6，int最大也就2*10^9。肯定会越界的，所以这里要用long long来计数。

[cpp]
include<stdio.h>
#include<string.h>
long long Merge(int *arr, int *ans, int Begin, int Mid, int End)
{
    int i,j,k;
    long long count = 0;
    for(i = Begin, j = Mid, k = Begin; i < Mid && j < End; ++k)
    {
        if(arr[i] <= arr[j])
            ans[k] = arr[i++];
        else
        {
            //数组2中跨越数组1的长度即为逆序对的个数
            count += Mid - i;
            ans[k] = arr[j++];
        }
    }
    for( ; i < Mid; ++i, ++k)
        ans[k] = arr[i];
    for( ; j < End; ++j, ++k)
        ans[k] = arr[j];
    memcpy(&arr[Begin], &ans[Begin], (End - Begin) * sizeof(int));
    return count;
}

long long MergeSort(int *arr, int *ans, int nLen)
{
    int i,l,e;
    long long count = 0;
    //步长跨度
    for(l = 1; l < nLen; l *= 2)
    {
        for(i = 0; i + l < nLen; i += l + l)
        {
            //第二部分的结束
            e = i + l + l > nLen ? nLen : i + l + l;
            count += Merge(arr, ans, i, i + l, e);
        }
    }
    return count;
}

int arr[1000001];
int ans[1000001];
int main()
{
    int i,n,t;
    long long count;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d",&n);
        for(i = 0; i < n; ++i)
            scanf("%d", &arr[i]);
        count = MergeSort(arr, ans, n);
        printf("%lld\n", count);
    }
    return 0;
}

补充：软件开发 , C++ ,