WA/MLE求助
查看原帖
WA/MLE求助
315873
Xxsr楼主2022/7/21 20:39

样例能过,数组如果少开一位就WA+RE,开到最大就爆空间,求助

#include<bits/stdc++.h>
#define ll  long long
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int mod=1e8-3;
const int N1=1e5+5;const int N2=1e4; 
int n,a[N2],b[N2],fa[N2],fb[N2],ans;//数组如果开到N1会MLE 
void merge_a(int l,int r){//给a数组排序 
	int i,j,k,m;
	if(l==r) return ;
	m=(l+r)/2;
	merge_a(l,m);
	merge_a(m+1,r);
	i=l,j=m+1,k=l;
	while(i<=m&&j<=r){
		if(a[i]>a[j]){
			fa[k]=a[j];
			fb[k]=b[j];//a,b数组同时操作 ,不影响a,b相对顺序 
			k++;j++;
		}
		else{
			fa[k]=a[i];
			fb[k]=b[k];
			k++;i++;
		}
	}
		while(i<=m){
			fa[k]=a[i];
			fb[k]=b[i];
			k++;i++;
		}
		while(j<=r){
			fa[k]=a[j];
			fb[k]=b[j];
			k++;j++;
		}
		for(int i=l;i<=r;i++) {a[i]=fa[i];b[i]=fb[i];}
}
void merge_b(int l,int r){//给数组b排序 
	int i,j,k,m;
	if(l==r) return ;
	m=(l+r)/2;
	merge_b(l,m);
	merge_b(m+1,r);
	
	i=l,j=m+1,k=l;
	while(i<=m&&j<=r){
		if(b[i]>b[j]){
			ans+=(m-i+1)%mod;//记录逆序对,即需要交换次数 
			fb[k]=b[j];k++;j++;
		}
		else{
			fb[k]=b[i];k++;i++;
		}
	}
		while(i<=m) {fb[k]=b[i];k++;i++;}
		while(j<=r) {fb[k]=b[j];k++;j++;}
		for(int i=l;i<=r;i++) b[i]=fb[i];
}
int main(){
	//freopen("P1966_2.in","r",stdin);
	cin>>n;
	rep(i,n) cin>>a[i];
	rep(i,n) cin>>b[i];
	merge_a(1,n);//第一个并归
	memset(fb,0,sizeof(fb));//清空fb再次利用 
	merge_b(1,n);//第二个并归 
	cout<<ans%mod;
	return 0;
}
2022/7/21 20:39
加载中...