Ricken @ 2019-08-15 22:36:16
#include<iostream>
using namespace std;
int a[1000001];
int r[1000001];//辅助数组
int ans=0;
void msort(int s,int t){//归并排序
if(s==t){
return;//如果只有一个数字则返回
}
int mid=(s+t)/2;
msort(s,mid);//分解左序列
msort(mid+1,t); //分解右序列
int i=s,j=mid+1,k=s;//接下来合并
while(i<=mid&&j<=t){
if(a[i]<=a[j]){
r[k]=a[i];
k++;
i++;
}
else{
r[k]=a[j];
k++;
j++;
ans+=mid-i+1;
}
}
while(i<=mid){//复制左边子序列剩余
r[k]=a[i];
k++;
i++;
}
while(j<=t){//复制右边子序列剩余
r[k]=a[j];
k++;
j++;
}
for(int i=s;i<=t;i++){
a[i]=r[i];
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
msort(1,n);
cout<<ans;
}
by XeCtera @ 2019-08-15 22:40:27
@Ricken 答案要开long long存
by 由比滨丶雪乃 @ 2019-08-15 22:42:07
ans 要开 longlong
归并没问题
by Ricken @ 2019-08-16 09:28:53
哦,我知道了,谢谢@bcr_233 @由比滨丶雪乃 。
by 香格里拉太子 @ 2019-08-23 16:59:23
在你这里学到了归并排序,哈哈