归并排序求逆序对

鸣谢:感谢zyf神犇告诉了我怎么用归并排序求逆序对!
另:这是我的第一份归并排序的代码,也是第一份求逆序对的代码

1. 什么是逆序对

对于一个包含N个非负整数的数组A[1..n],如果有i < j,且A[ i ]>A[ j ],则称(A[ i] ,A[ j] )为数组A中的一个逆序对。
例如,数组(3,1,4,5,2)的逆序对有(3,1),(3,2),(4,2),(5,2),共4个。
摘自度娘百科

2. 怎么用归并排序求逆序对

我们其实只要在归并排序的代码上加一句话就可以实现求逆序对了。

归并排序中,在合并左右两个区间时,对于右区间的每一个数字a[i],在左区间中有n[i]个比a[i]小的数字,那么n[1]+n[2]+n[3]+…就是跨越左右区间的逆序对数。而我们除了要求出跨越左右区间的逆序对数,还要求出左区间有多少对、右区间有多少对,这个我们就用递归实现。具体看代码吧,很难口头讲清楚。

3. 例题&代码

  1. 求逆序对 codvs – 1688
    传送门= ̄ω ̄=
    思路:模板题。
    代码:
#include <cstdio>
int n,arr[100005],c[100005],d[100005];
long long ans;
void mersort(int l,int r)
{
    if(l==r)return;
    int m=(l+r)>>1,a=l,b=m+1,cnt=l;
    mersort(l,m),mersort(m+1,r);
    c[m+1]=d[r+1]=1000000000;
    for(int i=l;i<=m;i++)c[i]=arr[i];
    for(int i=m+1;i<=r;i++)d[i]=arr[i];
    while(a<=m||b<=r)
        if(c[a]<=d[b])arr[cnt++]=c[a++];
        else arr[cnt++]=d[b++],ans+=(long long)(m-a+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    mersort(1,n);
    printf("%lld",ans);
    return 0;
}
  1. hzwer与逆序对 codevs – 4163
    传送门= ̄ω ̄=
    思路:同样模板题,数据大小大了10倍而已。
    代码:
#include <cstdio>
int n,arr[1000005],c[1000005],d[1000005];
long long ans;
void mersort(int l,int r)
{
    if(l==r)return;
    int m=(l+r)>>1,a=l,b=m+1,cnt=l;
    mersort(l,m),mersort(m+1,r);
    c[m+1]=d[r+1]=1000000000;
    for(int i=l;i<=m;i++)c[i]=arr[i];
    for(int i=m+1;i<=r;i++)d[i]=arr[i];
    while(a<=m||b<=r)
        if(c[a]<=d[b])arr[cnt++]=c[a++];
        else arr[cnt++]=d[b++],ans+=(long long)(m-a+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    mersort(1,n);
    printf("%lld",ans);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *