[hiho]二分·归并排序之逆序对

描述

在上一回、上上回以及上上上回里我们知道Nettle在玩《艦これ》。经过了一番苦战之后,Nettle又获得了的很多很多的船。
这一天Nettle在检查自己的舰队列表:
技术分享
我们可以看到,船默认排序是以等级为参数。但实际上一个船的火力值和等级的关系并不大,所以会存在A船比B船等级高,但是A船火力却低于B船这样的情况。比如上图中77级的飞龙改二火力就小于55级的夕立改二。
现在Nettle将按照等级高低的顺序给出所有船的火力值,请你计算出一共有多少对船满足上面提到的这种情况。

输入

第1行:1个整数N。N表示舰船数量, 1≤N≤100,000
第2行:N个整数,第i个数表示等级第i低的船的火力值a[i],1≤a[i]≤2^31-1。

输出

第1行:一个整数,表示有多少对船满足“A船比B船等级高,但是A船火力低于B船”。

样例输入

10
1559614248 709366232 500801802 128741032 1669935692 1993231896 369000208 381379206 962247088 237855491

样例输出

27

解题思路:归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序,然后再将这两半合并起来。在合并的过程中(设l<=i<=mid,mid+1<=j<=h),当a[i]<=a[j]时,并不产生逆序数;当a[i]>a[j]时,在前半部分中比a[i]大的数都比a[j]大,将a[j]放在a[i]前面的话,逆序数要加上mid+1-i。因此,可以在归并排序中的合并过程中计算逆序数.
注意范围,逆序数最大为n*(n-1)/2,结果用long long保存。
#include <stdio.h>

using namespace std;
const int N = 100000 + 5;

int a[N],tmp[N];
long long ans;

void Merge(int l,int m,int r)
{
    int i = l;
    int j = m + 1;
    int k = l;
    while(i <= m && j <= r)
    {
        if(a[i] > a[j])
        {
            tmp[k++] = a[j++];
            ans += m - i + 1;
        }
        else
        {
            tmp[k++] = a[i++];
        }
    }
    while(i <= m) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(int i=l;i<=r;i++)
        a[i] = tmp[i];
}

void Merge_sort(int l,int r)
{
    if(l < r)
    {
        int m = (l + r) >> 1;
        Merge_sort(l,m);
        Merge_sort(m+1,r);
        Merge(l,m,r);
    }
}

int main()
{
    int n;
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        ans = 0;
        Merge_sort(0,n-1);
        printf("%lld\n",ans);
    }
    return 0;
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。