POJ 0809 求逆序对数（归并排序求逆序数）

题目连接：http://dsa.openjudge.cn/sort/0809/

总时间限制: 500ms    内存限制: 65536kB

描述

对于一个长度为N的整数序列A，满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序。

请求出整数序列A的所有逆序对个数。

输入

输入包含多组测试数据，每组测试数据有两行

第一行为整数N(1 <= N <= 20000)，当输入0时结束

第二行为N个整数，表示长为N的整数序列

输出

每组数据对应一行，输出逆序对的个数

样例输入

5

1 2 3 4 5

5

5 4 3 2 1

1

1

样例输出

10

题意

赤裸裸地求逆序数。。。求逆序数算是算法编程题里常常遇到的问题了，一般情况下求逆序数有三种方法：归并排序、树状数组和线段树。由于博主渣渣还没有学会树状数组和线段树的运用，这里先给出归并排序的解法，待以后再来填这个坑。

AC代码

#include<bits/stdc++.h>
using namespace std;

int n,nums[],tmp[],cnt;

void mergesort(int l,int r)
{
    if(l>=r)    return;
    int m=(l+r)/;
    int i=l,j=m+,k=;
    while(i<=m&&j<=r){
        if(nums[i]>nums[j]){
            tmp[k++]=nums[j++];
            cnt+=m-i+;
        }
        else{
            tmp[k++]=nums[i++];
        }
    }
    while(i<=m) tmp[k++]=nums[i++];
    while(j<=r) tmp[k++]=nums[j++];
    for(i=;i<k;i++)    nums[i+l]=tmp[i];
}

void mergearray(int l,int r){
    if(l>=r)    return;
    int m=(l+r)/;
    mergearray(l,m);
    mergearray(m+,r);
    mergesort(l,r);
}

int main()
{
    while(~scanf("%d",&n)&&n){
        cnt=;
        for(int i=;i<n;i++){
            scanf("%d",&nums[i]);
        }
        mergearray(,n-);
        printf("%d\n",cnt);
    }
    return ;
}
           

注意

当时写的时候有好几个点没注意，所以WA了好几次，这里点出来给自己一个提醒。第一是关于归并排序，将左右两个子段合并的时候必须要新开一个O(n)的空间来存储临时数组，否则必须要通过交换元素来达到排序的目的，但是这样会超时。第二是关于逆序数的定义一定要看清，必须要严格满足i < j 且 Ai > Aj，也就是说i < j但是Ai = Aj时是不算逆序数的。