0

aサイズの配列の反転は、と を保持nするペアと呼ばれます。特定の配列の反転数をカウントする関数を C++ で実装しようとしています。マージ ソート アルゴリズムを変更するだけで、O(n log n ) 時間で実行される分割統治アプローチに従いました。これまでの私のコードは次のとおりです。(i,j)i<ja[i]>a[j]

long long int glob;

template< class T >
long long int merge( T *arr, int beg, int mid, int end ) {
  queue< int > left;
  queue< int > right;

  for( int i=beg; i<=mid; ++i ) {
    left.push( arr[i] );
  }
  for( int i=mid+1; i<=end; ++i ) {
    right.push( arr[i] );
  }

  int index=beg;
  int ret=0;

  while( !left.empty() && !right.empty() ) {
    if( left.front() < right.front() ) {
      arr[index++] = left.front();
      left.pop();
    } else {
      arr[index++] = right.front();
      right.pop();
      ret+=left.size();
    }
  }

  while( !left.empty() ) { arr[index++]=left.front();left.pop(); }
  while( !right.empty() ) { arr[index++]=right.front();right.pop(); }

  return ret;
}

template< class T >
void mergesortInvCount( T *arr, int beg, int end ) {
  if( beg < end ) {
    int mid = (int)((beg+end)/2);
    mergesortInvCount( arr, beg, mid );
    mergesortInvCount( arr, mid+1, end );
    glob += merge( arr, beg, mid, end );
  }
}

一部のテストケースでは正しい結果が得られますが、他のテストケースでは間違った出力が得られます。アルゴリズムを間違って理解したのでしょうか、それとも実装を間違えましたか? 誰か助けてくれませんか？前もって感謝します。

Test case: 2 1 3 1 2
Correct: 4
Mine: 6
4

2 に答える 2

2

コードのすべてのステップをチェックアウトしたわけではありませんが、あなたの行

if( left.front() < right.front() )

else-branch では、a(j)>a(i) の場合だけでなく、それらが等しい場合にも「ret」が増加することをお勧めします。これは、ケースの説明に対応していません。したがって、上記の行を次のように変更してみてください。

if( left.front() <= right.front() )

よろしく

于 2012-10-10T19:08:44.190 に答える
1

テスト

if( left.front() < right.front() )

する必要があります<=。左半分からの値の前に右半分から同じ値を移動し、そうでない反転をカウントします (そのような出現ごとに、左側の偽の反転の数がカウントされます)。あなたの例では、ペアを複製し、それぞれが1つのファントム反転を作成する必要があります。

于 2012-10-10T19:02:17.590 に答える