做法早就忘了，今回忆一波
#include<bits/stdc++.h> using namespace std; long long n,a[500005],b[500005],ans; void merge(int l,int r)//分解整个数组 { if(l==r)return;//分解得只有1个元素就收手 int mid=(l+r)/2; merge(l,mid); merge(mid+1,r); int i=l,j=mid+1,k=l; while(i<=mid&&j<=r)//只要没越界 if(a[i]<=a[j])b[k++]=a[i++];//不符合条件 else //符合条件 { b[k++]=a[j++]; ans+=mid-i+1;//？？？ } while(i<=mid) b[k++]=a[i++]; while(j<=r) b[k++]=a[j++];//处理剩余 for(int i=l; i<=r; i++) a[i]=b[i];//重新赋值 } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%lld",&a[i]); merge(1,n); printf("%lld",ans); return 0; }转载于:https://www.cnblogs.com/yige2019/p/11300567.html
相关资源：JAVA上百实例源码以及开源项目