为什么第二个点和第十个点WA了?
查看原帖
为什么第二个点和第十个点WA了?
246301
yunniw楼主2020/9/21 20:03
#include<stdio.h>
#include<stdlib.h>
long long res,tot;
long long num[1000000];
int a=1e8-3;
void mergesort(int left,int right);
void merge(int begin,int mid,int end);
int cmp(const void *a,const void *b);
typedef struct list{
	long long value;
	int seq;
}number;
number l1[1000000],l2[1000000];
int main(){
	int i;
	scanf("%lld",&tot);
	for(i=0;i<tot;i++) scanf("%lld",&l1[i].value),l1[i].seq=i;
	for(i=0;i<tot;i++) scanf("%lld",&l2[i].value),l2[i].seq=i;
	qsort(l1,tot,sizeof(l1[0]),cmp);
	qsort(l2,tot,sizeof(l2[0]),cmp);
	for(i=0;i<tot;i++) num[l2[i].seq]=l1[i].seq;
	mergesort(0,tot-1);
	printf("%lld",res);
	return 0;
}
void mergesort(int left,int right){
	if(left>=right) return;
	int mid=(left+right)/2;
	mergesort(left,mid);
	mergesort(mid+1,right);
	merge(left,mid,right);
	return;
}
void merge(int start,int mid,int end){
	int i,len1=mid-start+1,len2=end-mid,l=0,r=0;
	long long left[len1+10],right[len2+10];
	for(i=start;i<=mid;i++) left[i-start]=num[i];
	for(i=mid+1;i<=end;i++) right[i-mid-1]=num[i];
	for(i=start;i<=end;i++){
		if(l<len1&&r<len2){
			if(left[l]<=right[r]) num[i]=left[l++];
			else res+=(len1-l)%a,num[i]=right[r++];
		}else if(r<len2) num[i]=right[r++];
		else if(l<len1) num[i]=left[l++];
	}
	return;
}
int cmp(const void *a,const void *b){
	number *aa=(number*)a;
	number *bb=(number*)b;
	return((aa->value)>(bb->value)?1:-1);
}
2020/9/21 20:03
加载中...