【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.逆序对的数量的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-20获取apk的md5值有哪些方法?-icode9专业技术文章分享
- 2024-11-20xml报文没有传 IdentCode ,为什么正常解析没报错呢?-icode9专业技术文章分享
- 2024-11-20如何知道代码有没有进行 Schema 验证?-icode9专业技术文章分享
- 2024-11-20Mycat教程:新手快速入门指南
- 2024-11-20WebSocket入门:轻松掌握WebSocket基础
- 2024-11-19WebSocket入门指南:轻松搭建实时通信应用
- 2024-11-19Nacos安装资料详解:新手入门教程
- 2024-11-19Nacos安装资料:新手入门教程
- 2024-11-19升级 Gerrit 时有哪些注意事项?-icode9专业技术文章分享
- 2024-11-19pnpm是什么?-icode9专业技术文章分享