求助,全WA
查看原帖
求助,全WA
382691
德布劳内yyds楼主2021/5/27 14:44

求助

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

#include<bits/stdc++.h>
using namespace std;
 
int a[500004],b[500004],n;
long long ans;

void merge(int l,int r)
{
	//分解
	if(l==r)
		return ;
	int mid = (l+r)/2;
	merge(l,mid),merge(mid+1,r);
	
	//合并
	int i = l,j = mid+1,k = l;
	while(i<=mid && j<=r)
		if(a[i] <= a[j])
			b[k++] = a[j++];
		else
		{
			b[k++] = a[j++];
			ans+=mid-i+1;
		}	
	while(i <= mid)
	{
		b[k++] = a[i++];
	}
	while(j <= r)
	{
		b[k++] = a[j++];
	}
	for(int i =l;i<=r;++i)
	{
		a[i] = b[i]; 
	}
	return;
}

int main()
{
	scanf("%d",&n); 
    for(int i=1;i<=n;++i)
    	scanf("%d",&a[i]);
    merge(1,n);
    printf("%lld",ans);
    return 0;
}
2021/5/27 14:44
加载中...