文章
2
粉丝
362
获赞
1
访问
16.8k
使用合并排序+分治,直接双层循环会导致有数据超时
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int n;
int a[maxn],b[maxn];
long long ans = 0;
//归并排序
void merge(int L1,int R1,int L2,int R2){
int i = L1,j = L2;
int index = 0;//index为b数组的下标
while(i<=R1 && j<=R2){
if(a[i]<=a[j]){
b[index++] = a[i++];
}else{
b[index++] = a[j++];
ans += R1-i+1;//统计逆序对数
}
}
while(i<=R1) b[index++] = a[i++];
while(j<=R2) b[index++] = a[j++];
for(int i =0;i<index;i++){
a[L1+i] = b[i];//合并后的数组赋值回去
}
}
void mergeSort(int l,int r){
if(l == r) return;
int mid = (l+r)/2;
mergeSort(l,mid);
mergeSort(mid+1,r);
merge(l,mid,mid+1,r);
}
int main(){
scanf("%d",&n);
for(int i =0;i<n;i++){
scanf("%d",&a[i]);
}
mergeSort(0,n-1);
printf("%lld\n",ans);
return 0;
}
登录后发布评论
暂无评论,来抢沙发