計算數組中的反演次數

對於給定的問題陳述，我們需要計算數組中的反演次數，所以我嘗試應用一種算法，使用合併排序並計算合併時的反演次數以及排序時。雖然我的代碼給出了我作爲自己的解決方案饋給系統的測試用例的相同答案，但我在網上評判員Codechef上得到了錯誤的答案。請告訴我我的錯誤。計算數組中的反演次數

問題鏈接：http://www.codechef.com/COOK43/problems/LPAIR

代碼：

#include<iostream> 
using namespace std; 

long long int Merge(int* left,int* right,int* arr,int nl,int nr) 
{ 
    int i=0; 
    int j=0; 
    int k=0; 
    long long int cnt=0; 
    while(i<nl&&j<nr) 
    { 
     if(left[i]<=right[j]) 
     { 
      arr[k]=left[i]; 
      i++; 
     } 
     else 
     { 
      arr[k]=right[j]; 
      j++; 
      cnt+=nl-i; 
     } 
     k++; 
    } 
    while(i<nl) 
    { 
     arr[k]=left[i]; 
     i++; 
     k++; 
    } 
    while(j<nr) 
    { 
     arr[k]=right[j]; 
     j++; 
     k++; 
    } 
    return cnt; 
} 

long long int MergeSort(int *a,int len) 
{ 
    long long int cnt=0; 
    if(len<2) 
     return 0; 
    int mid=len/2; 
    int* left=new int[mid]; 
    int* right=new int[len-mid]; 
    for(int i=0;i<mid;i++) 
     left[i]=a[i]; 
    for(int i=mid;i<len;i++) 
     right[i-mid]=a[i]; 
    cnt+=MergeSort(left,mid); 
    cnt+=MergeSort(right,len-mid); 
    cnt+=Merge(left,right,a,mid,len-mid); 
    delete(left); 
    delete(right); 
    return cnt; 
} 

int main() 
{ 
    int n; 
    cin>>n; 
    int* fm=new int[n]; 
    for(int i=0;i<n;i++) 
     cin>>fm[i]>>fm[i]; 
    cout<<MergeSort(fm,n); 
}

來源

2014-02-21 InsaynAsasin

格式都捨不得虧的......空間上，大括號和評論是免費的，使用它們。 ;-) – DevSolar

這就是作弊..你知道..：P –

只是好奇，你是否計劃在解決'MergeSort'中的內存泄漏，然後再次提交？ – WhozCraig