归并排序
合并两个有序数组
p,mid
1 3 5 6 7 12
q
2 4 6 8 9 11
找到3比2大,则3之后的都比2大,所以2的逆序数就有mid-p+1个
// 2299.cpp : Defines the entry point for the console application. // #include <iostream> using namespace std; #define MAX 500000 int arr[MAX]; int tmp[MAX]; __int64 sum ; void merge(int le,int mi,int ri){ int p = le,q=mi+1,i=0; while(p<=mi&&q<=ri){ if(arr[p]>arr[q]) { tmp[i]=arr[q++]; sum+=mi-p+1; } else tmp[i]=arr[p++]; i++; } while(p <= mi) tmp[i++] = arr[p++]; while(q <= ri) tmp[i++] = arr[q++]; memcpy(arr+le,tmp,(ri-le+1)*sizeof(int)); } void mergeSort(int left,int right){ int mid; if(left<right) { mid = (right+left)/2; mergeSort(left,mid); mergeSort(mid+1,right); merge(left,mid,right); } } int main(int argc, char* argv[]) { //freopen("i://in.txt","r",stdin); int c,i; while(scanf("%d",&c)==1&&c){ sum = 0; for( i=0;i<c;i++) scanf("%d",arr+i); mergeSort(0,c-1); printf("%I64d\n",sum); } return 0; }