归并排序全wrong求助
查看原帖
归并排序全wrong求助
631896
Wangtsjo楼主2022/5/21 15:04

求助全wrong

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;
const int mod=99999997;
long long n,ans=0;
long long x[1000005],b[1000005];
struct abss{
	int v1,e1;
}a1[1000005],b1[1000005];
bool cmp1(abss aa,abss bb)
{
    return aa.v1<bb.v1;
}
void msort(int s,int t)
{
	if(s==t) return ;
	int mid=(s+t)>>1;
	msort(s,mid);msort(mid+1,t);
	int i=s,k=s,j=mid+1;
	while(i<=mid&&j<=t)
	{
		if(x[i]<=x[j]) {
			b[k]=x[i];k++;i++;
		}
		else{
			b[k]=x[j];k++;j++;ans=(ans+mid-i+1)%mod;
		} 
	}
	while(i<=mid){
		b[k]=x[i];i++;k++;
	}
	while(j<=t){
		b[k]=x[j];j++;k++;
	}
	for(int i=s;i<=t;i++)
	{
		x[i]=b[i];
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a1[i].v1);
		a1[i].e1=i;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b1[i].v1);
		b1[i].e1=i;
	}
	sort(a1+1,a1+n+1,cmp1);
	sort(b1+1,b1+n+1,cmp1);
	for(int i=1;i<=n;i++)
		x[b1[i].v1]=a1[i].v1;//题解里的离散化没有很懂
	msort(1,n);
	printf("%lld",ans);
	return 0;
}

谢谢大佬

2022/5/21 15:04
加载中...