【AcWing】788.逆序对的数量

2021/11/5 23:09:50

本文主要是介绍【AcWing】788.逆序对的数量,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:

给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i<j 且 a[i]>a[j],则其为一个逆序对;否则不是。

输入格式

第一行包含整数 n,表示数列的长度。

第二行包含 n 个整数,表示整个数列。

输出格式

输出一个整数,表示逆序对的个数。

数据范围

1≤n≤100000

样例输入

6
2 3 4 5 6 1

样例输出

5

标签:归并排序

解题思路:

利用归并排序统计每次调换左边比右边大的数时的次数即为逆序对数量

AC代码:

#include<stdio.h>
const int max=500100;
long long ans=0;
void merge(int s[],int L1,int L2,int R1,int R2){
    int index=0,temp[max];   //index置0
    int i=L1,j=R1;
    while(i<=L2&&j<=R2){
        if(s[i]<=s[j])
            temp[index++]=s[i++];
        else{
            temp[index++]=s[j++];
            ans+=L2-i+1;      //L2与i之间相差L2-i+1
        }
    }
    while(i<=L2)temp[index++]=s[i++];
    while(j<=R2)temp[index++]=s[j++];
    for(int i=0;i<index;i++){
        s[L1+i]=temp[i];     //更新原来的数组要以当前L1为起点
    }
}

void binary(int s[],int left,int right){
    if(left<right){
        int chief=(left+right)/2;
        binary(s,left,chief);
        binary(s,chief+1,right);
        merge(s,left,chief,chief+1,right);
    }
}

int main(){
    int n,s[max];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&s[i]);
    }
    binary(s,0,n-1);
    printf("%lld",ans);//long long输出用lld
    return 0;
}


这篇关于【AcWing】788.逆序对的数量的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程