【AcWing】 788. 逆序对的数量
数量 AcWing 逆序
2023-09-14 09:15:03 时间
788. 逆序对的数量
给定一个长度为 n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i个和第 j 个元素,如果满足 i<j 且 a[i]>a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数 n,表示数列的长度。
第二行包含 n个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1≤n≤100000,数列中的元素的取值范围 [1,109]。
输入样例:
6
2 3 4 5 6 1
输出样例:
5
思路:
代码样例:
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
int n;
int q[N],tmp[N];
long long merge_sort(int l, int r){
if(l>=r) return 0;
int mid=l+r>>1;
long long res=merge_sort(l,mid)+merge_sort(mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(q[i]<=q[j])tmp[k++]=q[i++];
else{
tmp[k++]=q[j++];
res+=mid-i+1;
}
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
return res;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>q[i];
cout<<merge_sort(0,n-1)<<endl;
return 0;
}
相关文章
- maven本地仓库配置了不起作用_仓库数量出错的原因
- [解决]:【TeamViewer作为个人用途免费,但仅可使用在有限数量的设备上。您已经到达可使用设备的上线】
- 433个量子比特!IBM发布最大超导量子计算机,比特数量超谷歌7倍
- Oracle查询:解答数据数量之谜(oracle查询数据数量)
- [问题解决]ALV可输入状态下输入金额/数量字段小数位数提前的问题详解编程语言
- ME21N-采购物料行项目相同的数量咋合并详解编程语言
- MySQL 最大连接数的优化(mysql连接数量)
- 限制Linux系统线程数量的限制(linux线程总数)
- 限制Linux文件打开数量的限制(linux文件打开数量)
- Linux 服务器CPU数量: 理解其性能优势(linuxcpu的个数)
- 揭秘Redis数量上限的真相(redis数量上限)
- 超越Redis数量上限:实现大数据存储(redis数量上限)
- MySQL分区:确定最佳数目(mysql分区数量)
- Oracle限制返回结果数量的方法(oracle限制查询条数)
- oracle数据库中几个数量字段的重要性(oracle几个数量字段)
- 解除Redis默认文件数量限制(redis默认文件数限制)
- Redis中键值对的数量由浅入深(redis 键值个数)
- Redis订阅数量大规模攀升(redis订阅数量多少)
- Redis秒杀数量突破100万(redis自增100万)