社区讨论

初学归并,求解为什么这个思路不对(

B3874[GESP202309 六级] 小杨的握手问题参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m03m27um
此快照首次捕获于
2024/08/21 16:47
2 年前
此快照最后确认于
2025/11/04 22:50
4 个月前
查看原帖
想直接转化为“正序对”求解但是不知道哪里出了问题)求调orz
CPP
#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;
} 

回复

1 条回复,欢迎继续交流。

正在加载回复...