哈理工OJ 2224 逆序對問題（利用歸并排序求逆序數對數）

題目連結：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2224

逆序對問題

Time Limit: 500 MS Memory Limit: 32768 K

Total Submit: 386(94 users) Total Accepted: 78(59 users) Rating: Special Judge: No

Description

給定 n 個數組成的數組，求其逆序對的總數。

逆序對定義為，存在 (i, j) 滿足 i < j 且 A[i] > A[j] 的二進制組的數目。

Input

第一行包含一個整數，表示數組的項數。

接下來的一行，包含 n 個數（2 <= n <= 100000），依次表示 A[i](A[i] <= 10^9)。

Output

輸出一行表示對應的答案。。

Sample Input

5

1 3 2 5 4

Sample Output

2

Source

“誠德軟體杯”哈爾濱理工大學第四屆ACM程式設計團隊賽

【思路分析】利用歸并排序的特性求逆序數的對數。

【AC代碼】

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX 1000010
#define MN 1000000050
#define LL long long
LL sum;
int a[MAX];
int L[MAX/],R[MAX/];

void merge(int A[],int p,int q,int r)
{
    int n1=q-p+,n2=r-q,i,j;
    for (i=; i<=n1; i++)
        L[i]=A[p+i-];
    for (i=; i<=n2; i++)
        R[i]=A[q+i];
    R[n2+]=L[n1+]=MN;
    i=j=;
    for (int k=p; k<=r; k++)
    {
        if(L[i]<=R[j])
            A[k]=L[i++];
        else
        {
            A[k]=R[j++];
            sum+=n1-i+;
        }
    }
}

void merge_sort(int A[],int p,int r)
{
    int q;
    if(p<r)
    {
        q=(p+r)>>;
        merge_sort(A,p,q);
        merge_sort(A,q+,r);
        merge(A,p,q,r);
    }
}

int main()
{
    int t,i,n,num,k;
    while(~scanf("%d",&n))
    {

        sum=;
        for(i=; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        merge_sort(a,,n);
        printf("%lld\n",sum);
    }
    return ;
}