洛谷 P1908 逆序对

佚名 6年前 (2019-04-24) 随笔 1302人围观抢沙发百度已收录

\[传送门qwq\]

题目描述

猫猫\(TOM\)和小老鼠\(JERRY\)最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

最近，\(TOM\)老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：

对于给定的一段正整数序列，逆序对就是序列中\(a_i\)>\(a_j\)且\(i\)<\(j\)的有序对。

知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

Update:数据已加强。

输入输出格式

输入格式：

第一行，一个数\(n\)，表示序列中有\(n\)个数。

第二行\(n\)个数，表示给定的序列。序列中每个数字不超过\(10^9\)

输出格式：

给定序列中逆序对的数目。

思路

逆序对是什么东西呢，在题目已经给出介绍了

对于给定的一段正整数序列，逆序对就是序列中\(a_i\)>\(a_j\)且\(i\)<\(j\)的有序对。

比如你有一个\(a\)数组，如果在这个数组中中\(a[i]\)>\(a[j]\)并且\(i\)<\(j\)，我们就称它是一个逆序对

这个题就是要求我们求出输入的数中逆序对的数量

求逆序对的方法有很多种，可以用树状数组，也可以用线段树，但由于本蒟蒻没有学过这俩玩意儿，所以只会用归并排序，那么归并排序又是什么呢

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

可以来这里理解一下什么是归并排序

那么归并排序有什么优点呢？

* 归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略
* 归并排序是稳定排序
* 归并排序的最好，最坏，平均时间复杂度均为O(\(nlogn\))。

如何实现求逆序对？？

假设我们手头有两个已经从小到大排好序的数组，且他们分别是原来的一段大数组的前半段和后半段，现在我们的比较到了X,Y位置

假使X>Y则其必然构成一对逆序对，与此同时我所画出的红色的这一段的的数均大于Y，所以逆序对的数量就要加上这一段的长度

而对整个数组都归并排序完毕后最终就可以得到逆序对的和

代码

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

int n;
long long ans;
int a[5000007],b[5000007];

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

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;
}

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        a[i]=read();
    }
    sort(1,n);
    printf("%lld",ans);
    return 0;
}