初学归并,求解为什么这个思路不对(
查看原帖
初学归并,求解为什么这个思路不对(
956316
77Glorious楼主2024/8/21 16:46

想直接转化为“正序对”求解但是不知道哪里出了问题)求调orz

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

void ms(int l,int r)//mergesort归并排序 
{
	int mid=l+(r-l)/2;
	if(l==r) return;//只剩一个数就返回 
	ms(l,mid); ms(mid+1,r);
	int i=l,j=mid+1,k=0;//i左j右指针 
	//ai<aj才可以握手 
	while(i<=mid && j<=r)//同时填入左右 
	{
		if(a[i]<a[j])
		{
			ans+=mid-i+1;//计算正序对( 
			b[++k]=a[i++];	//填入小的数 
		} 
		else b[++k]=a[j++];
	}
	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]; //a赋值为排序后 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	ms(1,n);
	//寻找正序对 
	cout<<ans;
} 
2024/8/21 16:46
加载中...