题目(2)(最接近神的人)
思路
这是一道标准的逆序列题,用归并排序即可。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; long long int a[500001],r[500001],ans=0,n; void gsort(int s,int t) { if(s==t) return ; int mid=(s+t)/2; gsort(s,mid); gsort(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]; i++; k++; } else { r[k]=a[j]; j++; k++; ans=ans+mid-i+1; } } while(i<=mid) { r[k]=a[i]; i++; k++; } while(j<=t) { r[k]=a[j]; j++; k++; } for(int i=s;i<=t;i++) a[i]=r[i]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; gsort(1,n); cout<<ans<<endl; return 0; }