http://poj.org/problem?id=2299
#include <iostream> #include <stdio.h> #include <string.h> #include <string> #include <math.h> #include <queue> #include <stack> #include <map> #include <set> #include <algorithm> using namespace std; #define N 500050 long long cnt; void Msort(int A[],int T[],int low,int high){ if(high - low > 1){ int mid = low + (high-low)/2; Msort(A,T,low,mid); Msort(A,T,mid, high); int i = low; int j = mid; int k = low; // while(i<mid || j<high){ // if(j>=high || (i<mid && S2[i]<=S2[j])){ // T[k++] = S2[i++]; // }else{ // T[k++] = S2[j++]; // cnt += (mid-i); // } // } while(i<mid && j<high){ if(A[i]<=A[j]) { T[k++] = A[i++]; } else{ T[k++] = A[j++]; cnt += (mid-i); } } while(i<mid){ T[k++] = A[i++]; } while(j<high){ T[k++] = A[j++]; } for(int i=low;i<high;i++) A[i] = T[i]; } } int f[N]; int ans[N]; int main() { //freopen("/Users/a1/Public/20150717/20150717/in.txt","r",stdin); int n; while(scanf("%d",&n) && n){ cnt = 0; for(int i=0;i<n;i++){ scanf("%d",&f[i]); } // for(int i=0;i<n;i++) // printf("%d ",f[i]); Msort(f,ans,0,n ); //左闭右开 // for(int i=0;i<n;i++) // printf("%d ",ans[i]); // } printf("%lld\n",cnt); } return 0; }