当前位置:   article > 正文

SCAU 数据结构 18746 逆序数

18746 逆序数

18746 逆序数

Description
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。
一个排列中逆序的总数就称为这个排列的逆序数。逆序数是课程线性代数的一个知识点。
现在给定一个排列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称ai和aj为一个逆序,请求出排列的逆序数。
输入格式
第一行为n,表示排列长度。(1=<n<=100000)
第二行有n个整数,依次为排列中的a1,a2,…,an。所有整数均在int范围内。
输出格式
一个整数代表排列的逆序数。
输入样例
4
3 2 3 2
输出样例
3
提示
注意答案的数据范围。

#include<iostream>
using namespace std;
int n,a[100005],temp[100005];//a是原数组,temp是临时数组
long long sum=0;//注意逆序数数据范围

void mergeSort(int left,int right) {//a、temp、sum都是全局变量可以不用传
    if(right-left>1) {
        int mid = left+(right-left)/2;
        int temp_left=left,temp_right=mid,i=left;
        //temp_left和temp_right分别为左右两个待合并数组的遍历脚标,i为合并后数组的遍历脚标
        //分治
        mergeSort(left,mid);
        mergeSort(mid,right);
        //归并
        while(temp_left<mid || temp_right<right) {
            if(temp_right>=right||(temp_left<mid&&a[temp_left]<=a[temp_right])) {
                temp[i++]=a[temp_left++];//[]和后置++优先级都为1,左结合
            } else {
                temp[i++]=a[temp_right++];
                sum += mid-temp_left;//在归并排序的基础上加上这一句
                //当右数组的元素要往前排的时候左数组中有mid-temp_left个数比他大,构成逆序
            }//明确"左右两个数组分别都是有序的"就不难理解这一方法了
        }
        for(i=left; i<right; i++) {//从临时数组复制回原数组
            a[i]=temp[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int i;
    cin>>n;
    for(i=0; i<n; i++) {
        cin>>a[i];
    }
    mergeSort(0,n);
    cout<<sum;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 根据题目给的范围sum要用long long
  • 本题在归并排序的基础上加上这一句sum += mid-temp_left;即可
  • 时间复杂度为O(nlogn) 需要额外大小为n的空间
  • []和后置++优先级都为1,左结合
  • 详见注释
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/761698
推荐阅读
相关标签
  

闽ICP备14008679号