解题报告 P1908 逆序对

题目内容

P1908

前言:归并排序

这里把归并排序写了留给我这个蒟蒻以后看

归并排序:时间复杂度O(n\log n),空间复杂度O(n)的稳定排序算法。(试了一下,模板题速度比stl的sort还快,快排123ms,归并105ms,加上40行优化后77ms)

思想是递归+二分

将一个无序的序列先挨次递归分成两端两端,使左右两端先有序,然后从底往上依次合并小的分段序列,具体操作如下:

设需操作的序列左端下标为l,右端下标为r,则定义一变量mid=l+r>>1(代表l+r的和除以2,使用二进制优化常数),则左端序列是[l,mid],右端是[mid+1,r],再分别对其递归式地分割。

合并时定义三个指针l,r和k,分别指向左端序列的开头,右端序列的开头和新的临时序列b的对应位置,然后比较a[i]a[j]的值,如果a[i]<a[j],则将a[i]放入b序列中,并将指针i,k各加一,如果a[i]>a[j],同理,将a[j]放入b序列中,并将指针j,k各加一。

为什么可以这样处理,因为需要合并的两端的序列都已经是有序的了(经过上一层递归处理过),再这样合并即可。

如果有剩余,则继续将i指针指向的内容和j指针指向的内容放入b序列中排好序的元素重新复制回a序列。

,然后再将b序列中排好序的元素重新复制回a序列。

网图:
简书@CoderJed(https://www.jianshu.com/p/33cffa1ce613)

代码实现:

#include <cstdio>
using namespace std;

const int maxn=1e5+4;

int a[maxn],b[maxn],N;//开局时先定义两个数组,a存储数据,b为归并时要用的辅助数组

inline int read()//快读
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

void msort(int l, int r)//排序函数
{
    if(l==r) return;//如果l=r,那么return
    int mid=l+r>>1,i=l,j=mid+1,k=l;//定义mid变量和i,j,k三个指针
    msort(l,mid);msort(mid+1,r);//递归处理左和右序列
    while(i<=mid&&j<=r)//开始归并
    {
        if(a[i]<=a[j]) b[k++]=a[i++];//如果a[i]<=a[j],将a[i]放入b序列并将指针后移
        else b[k++]=a[j++];//否则将a[j]放入序列
    }
    while(i<=mid) b[k++]=a[i++];//处理剩下的
    while(j<=r) b[k++]=a[j++];//处理剩下的
    for(int ii=l;ii<=r;ii++) a[ii]=b[ii];//复制结果回a数组
}

int main()
{
    N=read();
    for(int i=1;i<=N;i++)
        a[i]=read();
    msort(1,N);
    for(int i=1;i<=N;i++)
        printf("%d ",a[i]);
    return 0;
}

解题思路

首先要搞懂什么是逆序对

逆序对就是序列中a_i>a_j且i<j的有序对

搞清楚了什么是逆序对,让我们看看为什么归并排序能帮助我们解题

题目要求寻找的是逆序对的数目,而我们在做每一次合并的时候都会做a[i]是否大于a[j]的判断,通过这样的判断我们就可以找出逆序对的对数,如果a[i]大于a[j],那么由于合并过程中两边的序列都是有序的,那么就一定会产生mid-i+1对逆序对:

看下面例子:

要合并的序列:1 2 5 6 (下标为i)
             3 4 5 7 (下标为j)

开始合并:
step 1: i=1, j=5, 1<3, 将1放入b序列中并i++
step 2: i=2, j=5, 2<3, 将2放入b序列中并i++
step 3: i=3, j=5, 5>3, 由于左序列后面所有的数都大于3,因此会产生5->3,6->3两个逆序对,
                       即mid-i+1个,且将3放入b序列中并j++
step 4: i=3, j=6, 5>4, 由于左序列后面所有的数也都大于4,因此会产生5->4,6->4两个逆序
                       对,也是mid-i+1个,且将4放入b序列中并j++
step 5: i=3, j=7, 5=5, 将5放入b序列中并i++
step 6: i=4, j=7, 6>5, 产生1个逆序对6->5,将5放入b序列中并j++
step 7: i=4, j=8, 6<7, 将6放入b序列中,由于i已经到达上限,故结束此过程,将剩余的7放入b序列

因此我们得到一个规律,每当发现a[i]>a[j]时,会产生mid-i+1个逆序对,计入ans即可,要注意ans要开long long,否则会炸。

代码如下:

#include <cstdio>
using namespace std;
typedef unsigned long long ll;

const int maxn = 5e5 + 10;
ll ans = 0;
int a[maxn], b[maxn], n;

void msort(int l, int r)//归并排序,只是加了记录ans而已
{
    if(l==r) return;
    int mid=(l+r)/2,i=l,j=mid+1,k=l;
    msort(l,mid);msort(mid+1,r);
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) b[k++]=a[i++];
        else b[k++]=a[j++],ans+=mid-i+1;//记录ans
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(int ii=l;ii<=r;ii++) a[ii]=b[ii];
}

int main()
{
#ifndef ONLINE_JUDGE//本地调试使用
    freopen("1908.in", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    msort(1, n);
    printf("%llu\n", ans);//输出记得llu
    return 0;
}

反思

第一次打归并排序,其实归并排序本质上也就是一个分治的思想,将一个大的序列细分,逐个变为有序再最后合并。

逆序对,emm,仔细读题