#题解逆序对

miaohongxuan · 2020-04-22 21:41:38 · 个人记录

我们先来读题

题目描述

猫猫 TOM和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 a_i>a_j 且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强

输入格式

第一行，一个数 nn，表示序列中有 nn个数。第二行 nn个数，表示给定的序列。序列中每个数字不超过 10^9。

输出格式

输出序列中逆序对的数目。

输入输出样例

输入 #1

6 5 4 2 6 3 1

输出 #1

说明/提示

对于 25% 的数据，n≤2500

对于 50% 的数据，n≤4×10^4

对于所有数据，n≤5×10^5

请使用较快的输入输出应该不会 O(n^2)过 50 万吧 by chen\_zhe

具体实现

在我们讲解这道题之前，先来了解一个排序算法——归并排序，这一次我们就要利用归并排序解题。归并排序的核心是对有序数组的合并，在合并过程中，就有i和j而i的值是l\~mid,j的值是mid+1\~r,所以他们就构成了天然有序的i和j，接下来，只需要找到a~i~ > a~j~,而在a~i~ > a~j~时，a~i+1~ > a~j~，a~i+2~ > a~j~……一直到a~mid~ > a~j~，此时就有了mid-i+1个逆序对，加到统计变量中即可。

归并排序完整代码

int a[1000000],t[1000000];
void merge(int l,int mid,int r){
    //l~mid
    //mid+1 ~r 
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            t[k++]=a[j++];
        }else{
            t[k++]=a[i++];
        }
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    // t[l~r]  
    for(int x=l;x<=r;x++){
        a[x]=t[x];
    }

}

void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  //1. 左右两边有序
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  //O（n） 合并
  merge(l,mid,r);
}

先加上一个变量sumlong long sum=0;~~不要问我干嘛用long long，自己试去~~ 接下来找到判断大小的那一段。

    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            t[k++]=a[j++];
        }else{
            t[k++]=a[i++];
        }
    }

在t[k++]=a[j++]; 后面加上 sum+=mid-i+1;就变成了……

    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            t[k++]=a[j++];
            sum+=mid-i+1;
        }else{
            t[k++]=a[i++];
        }
    }

——————————————————————————————————————————————— 至此函数的改变都改好了~~是不是很简单？~~ 我们再来把输入输出和函数调用完善一下。主函数代码：

int main(){
    //freopen("1.in","w",stdin);定义输入文件，这个语句执行一次后，一定要注释掉，不然你会疯的
    //freopen("1.in","r",stdin);读取输入文件
    //freopen("1.out","w",stdout);这些比赛时才用得着，了解一下吧
    //**********文件**************

    long n=0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    mergeSort(0,n-1);
    cout << sum;

    return 0;//养成良好的习惯 
}

完整代码

#include<bits/stdc++.h>//万能头文件 
using namespace std;
int a[500010],t[500010],n;
long long sum=0;
void merge(int l,int mid,int r){
    //l~mid
    //mid+1 ~r 

    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            t[k++]=a[j++];
            sum+=mid-i+1;
        }else{
            t[k++]=a[i++];
        }
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    // t[l~r]  
    for(int x=l;x<=r;x++){
        a[x]=t[x];
    }

}
void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  merge(l,mid,r);
}

int main(){
    //freopen("1.in","w",stdin);定义输入文件，这个语句执行一次后，一定要注释掉，不然你会疯的
    //freopen("1.in","r",stdin);读取输入文件
    //freopen("1.out","w",stdout);这些比赛时才用得着，了解一下吧
    //**********文件**************

    long n=0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    mergeSort(0,n-1);
    cout << sum;

    return 0;//养成良好的习惯 
}

有兴趣的小伙伴可以自己做完后在洛谷提交通道提交哦。

我的第一次提交代码

#include<bits/stdc++.h>//万能头文件 
using namespace std;
int a[500010],t[500010],n,sum=0;
void merge(int l,int mid,int r){
    //l~mid
    //mid+1 ~r 

    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            t[k++]=a[j++];
            sum+=mid-i+1;
        }else{
            t[k++]=a[i++];
        }
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    // t[l~r]  
    for(int x=l;x<=r;x++){
        a[x]=t[x];
    }

}
void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  merge(l,mid,r);
}

int main(){
    //freopen("1.in","w",stdin);定义输入文件，这个语句执行一次后，一定要注释掉，不然你会疯的
    //freopen("1.in","r",stdin);读取输入文件
    //freopen("1.out","w",stdout);这些比赛时才用得着，了解一下吧
    //**********文件**************

    long n=0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    mergeSort(0,n-1);
    cout << sum;

    return 0;//养成良好的习惯 
}

估计你是一行一行对才能找到，这也是为什么让你们用long long类型 int a[500010],t[500010],n,sum=0; ^ ^ 我用的是int类型发现没有？所以就过不了。数据类型坑死人呐[大哭]，做题时一定要仔细读题，数据范围也别漏，才能一次通过，取得AC。加油(ง •_•)ง

#题解 逆序对