50分求助
查看原帖
50分求助
1428771
Eternal_Missing楼主2024/9/2 22:00

为什么有一半RE了?

#include<bits/stdc++.h>
using namespace std;
int n,a[50010],temp[50010];
long long ans;
void merge(int l,int mid,int r){
	int i=l,j=mid+1,p=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j])
			temp[p++]=a[i++];
		 else{
		 	temp[p++]=a[j++];
		 	ans+=mid-i+1;
		 }
	}
	while(i<=mid)
		temp[p++]=a[i++];
	while(j<=r)
		temp[p++]=a[j++];
	for(int i=l;i<=r;i++)
		a[i]=temp[i];
}
void merge_sort(int l,int r){
	if(l==r)
		return ;
	int mid=(l+r)/2;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	merge(l,mid,r);
} 
int main() {
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	merge_sort(1,n);
	cout<<ans;
	return 0;
}

用的归并排序

2024/9/2 22:00
加载中...