【题解】P1908 -归并排序求逆序对和

2018-10-22 21:26:32


在解题之前,先让我们来看一看本题会用到而萌新可能不懂的几个事项:

本题大意:对于给定的无序数组,求出经过最少多少次相邻元素的交换之后,可以使数组从小到大有序

对于逆序对的解释:两个数(a, b)的排列,若满足a > b,则称之为一个逆序对

归并排序的思想:先把每个数看成一段,然后两两合并成一个较大的有序数组,再把较大的两两合并,直到最后成为一个有序数组

归并排序复杂度:$ O(nlogn) $

接下来就是我们解题的步骤了:

根据排序算法,我们知道如果相邻的两个元素满足前一个大于后一个便会交换一次,由于题目要求排序后是单调递增,所以我们可以将这道题看做求原数组逆序对的数量

举一个归并排序的例子:

假设初始数组为4 2 1 3

先把每一个数单独分成一组,即(4) (2) (1) (3)

接着两两合并,即(2 4) (1 3)

最后合成一个有序的数组,即(1 2 3 4)

不难发现,在排序过程中,若某个数向前移动了N位,则必定存在N个逆序数,如上面例子中,数字1由原先的第三位移到了第一位,前移了两位,则存在(2 1)和(4 1)两个逆序

而根据题意,我们只需要在归并排序的过程中把这个数记下来即可

接下来上一下代码

顺便安利一波自己的io模板:自测结果:不加io优化跑了1108ms,加了优化后仅跑了797ms(看近期大多数的提交都是1200ms+ ,快一点的也都是1000ms+,797ms应该算是比较快的)

io模板详解链接:https://twi.blog.luogu.org/duliu-io

#include<cstdio>
using namespace std;
#define ll long long

namespace io {  //io模板详见个人博客
#define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
    const int SIZ = 1 << 21 | 1;
    char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110], c;
    int fr;
    inline void out() {
        fwrite(obuff, 1, oS - obuff, stdout);
        oS = obuff;
    }
    template<class Type>
    inline void read(Type &x) {
        x = 0;
        Type y = 1;
        for (c = gc(); (c > '9' || c < '0') && c != '-'; c = gc());
        c == '-' ? y = -1 : x = (c & 15);
        for (c = gc(); c >= '0' && c <= '9'; c = gc())
            x = x * 10 + (c & 15);
        x *= y;
    }
    template<class Type>
    inline void print(Type x, char text = '\n') {
        if (x < 0)
            *oS++ = '-', x *= -1;
        if (x == 0)
            *oS++ = '0';
        while (x)
            fu[++fr] = x % 10 + '0', x /= 10;
        while (fr)
            *oS++ = fu[fr--];
        *oS++ = text;
        out();
    }
}
using namespace io;  //以上为玄(du)学(liu)优(ka)化(chang)

ll ans[500010], mem[500010], anss;
int n;

void merge(int lo, int mid, int hi) {
    int i = lo, e = mid + 1, k = lo;
    while (i <= mid && e <= hi) {
        if (ans[i] <= ans[e])
            mem[k++] = ans[i++];
        else
            anss += e - k, mem[k++] = ans[e++]; //求逆序对和
    }
    while (i <= mid)
        mem[k++] = ans[i++];
    while (e <= hi)
        mem[k++] = ans[e++];
    for (i = lo; i <= hi; ++i)
        ans[i] = mem[i];
}

void merge_sort(int x, int y) {
    if (x < y) {
        int mid = (x + y) / 2;
        merge_sort(x, mid);
        merge_sort(mid + 1, y);
        merge(x, mid, y);
    }
}

int main() {
    read(n);
    for (register int i = 0; i < n; ++i)
        read(ans[i]);
    merge_sort(0, n - 1);
    print(anss);
    return 0;
}

我们的信条就是,用最短的码长,写出跑的最快的代码(不算io优化本人代码码长仅为0.8kb,在题解中也算是比较短的代码了)

码风诡异请不要在意QAQ

这道题就到这里,让我们下一道题见(发出咕咕咕的声音)