题意:输入数组长度,及数组元素,求逆序对个数
1.归并排序方法:
#include<bits/stdc++.h> using namespace std; long long cnt=0; int a[10010]; int b[10010]; void Mergesort(int l,int r) { if(l==r)return ; int mid=(l+r)>>1; Mergesort(l,mid); Mergesort(mid+1,r); int i=l,j=mid+1; for(int k=l;k<=r;k++){ if(j>r||i<=mid&&a[i]<=a[j]) b[k]=a[i++]; else b[k]=a[j++],cnt+=mid-i+1; } for(int k=l;k<=r;k++) a[k]=b[k]; } int main() { int n; while(scanf("%d",&n)!=EOF&&n) { cnt=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); Mergesort(1,n); printf("%lld\n",cnt); } return 0; }