如果直接暴力的话 n2一定会超时
考虑归并，分治的思想
// // main.cpp // wzazzy // // Created by apple on 2018/10/23. // Copyright © 2018年 apple. All rights reserved. // #include<stdio.h> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<string.h> #include<queue> #include<stack> #include<list> #include<map> #include<set> #include<vector> typedef long long int ll; const int maxn =50000+10; const int maxm=10000; const int mod =1e9+7; const int INF=0x3f3f3f3f; int ans=0; void solve(int *a,int *t,int x,int y) { if(y-x>1) { int m=(y+x)>>1; int p=x,q=m,i=x;; solve(a,t,x,m); solve(a,t,m,y); while(p<m||q<y) { if(q>=y||(p<m&&a[p]<=a[q])) t[i++]=a[p++]; else t[i++]=a[q++],ans+=m-p; } for(int i=x;i<y;i++) a[i]=t[i]; } } int main(int argc, const char * argv[]) { int n;scanf("%d",&n); int a[maxn],t[maxn]; for(int i=0;i<n;i++) scanf("%d",&a[i]); solve(a,t,0,n); printf("%d\n",ans); return 0; }
