文章

2

粉丝

362

获赞

1

访问

16.8k

头像
使用合并排序+分治
P1584 杭州电子科技大学机试题
发布于2020年5月31日 16:39
阅读数 8.1k

使用合并排序+分治,直接双层循环会导致有数据超时

#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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发