归并排序做但是超时,该怎么改???
  • 板块P1908 逆序对
  • 楼主肖睿航
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/5/8 13:20
  • 上次更新2023/11/4 23:33:35
查看原帖
归并排序做但是超时,该怎么改???
69143
肖睿航楼主2021/5/8 13:20

这是我第一次的逆序对,但感觉没什么错误,请各位帮我大佬康康

代码如下:

#include<bits/stdc++.h>
using namespace std;
long long n,s1[500050],s2[500020],cnt;
void merge(int L,int  R,int Mid){
	long long i = L,j = Mid + 1,k = L;
	while(i <= Mid && j <= R){
		if(s1[i] <= s1[j])s2[k ++]=s1[i ++];
		else{
			 cnt += Mid - i + 1; 
			 s2[k ++] = s1[j ++];
		} 
	}
	while(i <= Mid)s2[k ++] = s1[i ++];
	while(j <= R)s2[k ++] = s1[j ++];
	for(int i=L; i<=R; i++)s1[i] = s2[i];
}
void mergesort(int L,int R){
	if(L<R){
		long long Mid = (L + R) / 2;
		mergesort(1,Mid);mergesort(Mid+1,R);
		merge(L,R,Mid);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%d",&s1[i]);
	mergesort(1,n);
	printf("%d ",cnt);
	return 0;
}
2021/5/8 13:20
加载中...