1

特定の問題ステートメントでは、配列内の反転数を計算する必要があるため、マージソートを使用してアルゴリズムを適用し、マージ中およびソート時に反転数を計算しようとしました。私のコードは、システムに入力したテスト ケースに対して自分のソリューションと同じ回答を返しますが、オンライン ジャッジである 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);
}
4

2 に答える 2

0

これは正しいアプローチであり、非常に単純な問題があります。n = 10 5の反転の数が整数をオーバーフローする可能性があります。それをどのように修正できるかを考えてください。

于 2014-02-21T11:55:05.250 に答える