本文共 1202 字，大约阅读时间需要 4 分钟。

#include <cstdlib>#include <iostream>#include <cstdio>using namespace std;const int MAX = 500001;int value[MAX];int temp[MAX];__int64 result = 0;void merge(int left, int mid, int right){ int k = 0; int i=left; int j=mid + 1; while(i<=mid && j<=right) { if(value[i] <= value[j]) temp[k++] = value[i++]; else { temp[k++] = value[j++]; result += mid - i + 1; } } while(i <= mid) temp[k++] = value[i++]; while(j <= right) temp[k++] = value[j++]; for(int i=0; i<=right - left; i++) value[i + left] = temp[i];}void mergeSort(int left, int right){ if(left < right) { int mid = (left + right) >> 1; mergeSort(left, mid); mergeSort(mid + 1, right); merge(left, mid, right); }}int main(int argc, char *argv[]){ int n, i; //freopen("input.txt", "rt", stdin); //freopen("output.txt", "wt", stdout); while(scanf("%d", &n) && n != 0) { result = 0; for(int i=0; i<n; i++) scanf("%d", &value[i]); mergeSort(0, n - 1); printf("%I64d/n", result); } return EXIT_SUCCESS;} 

转载地址：http://ldkqb.baihongyu.com/