首先，很容易看出的一点是 的暴力是过不了的，对吧。
我们可以通过归并排序的方式来解决这个问题。
在归并排的过程中可以一批一批的算出结果，而不是一个一个。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int n,a[N],tmp[N];
long long ans;
void merge_sort(int s,int e) {
if(s==e) return;
int mid=(s+e)/2,s1=s,s2=mid+1,t=s;
merge_sort(s,mid);
merge_sort(mid+1,e);
while(s1<=mid&&s2<=e)
if(a[s1]<=a[s2]){
tmp[t++]=a[s1++];
}else{
tmp[t++]=a[s2++];
ans+=mid-s1+1;
}
while(s1<=mid)
tmp[t++]=a[s1++];
while(s2<=e)
tmp[t++]=a[s2++];
for(int i=s;i<=e;i++)
a[i]=tmp[i];
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
merge_sort(1,n);
cout<<ans;
return 0;
}
暂无评论