题目描述
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数n,表示数列的长度。
第二行包含 n 个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1≤n≤1000000
样例
输入样例:
6
2 3 4 5 6 1
输出样例:
5
算法1
(归并排序)
题的测试样例很大如果使用int会溢出,使用double型存储数据
C++ 代码
#include<iostream>
using namespace std;
int p[1000010];
double res=0;
void merge_sort(int q[],int l,int r){
if(l>=r) return;
int temp[r-l+1];//归并排序空间复杂度o(n),需要开数组临时存放变量
int mid = l + r >> 1;//分界点为中间的结点
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1;//双指针两数组归并
while(i<=mid&&j<=r)//任一指针走到头
if(q[i]>q[j]) res+=mid-i+1,temp[k++]=q[j++];
//将更小的先放入temp数组,若q[i]>q[j],则q[i]到q[mid]都与q[j]成逆序对
//例如[3,4,1,2]中q[0]>q[2],则q[0],q[1]都与q[2]成逆序对,而q[mid]与q[i]有mid-i+1个数字,因此逆序对增加mid-i+1
else
{temp[k++]=q[i++];}
while(i<=mid) temp[k++]=q[i++];//如果i没走到头,继续将剩余的元素放入temp数组
while(j<=r) temp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j];//将临时存放的数组放回要排序的数组
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&p[i]);
}
merge_sort(p,0,n-1);
// for(int i=0;i<n;i++){
// printf("%d ",p[i]);
// }
//调试代码
printf("%.0f",res);
return 0;
}
res用long long int 更好吧
我也理解了 很不错奥
大佬的方法简便,让我理解了,谢谢。