C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++STLでSetを使用して反転をカウントする

このチュートリアルでは、C++STLのセットを使用して転倒をカウントするプログラムについて説明します。

反転カウントは、配列が完全にソートされるまでの距離の尺度です。配列がすでにソートされている場合、反転カウントは0になります。

例

#include<bits/stdc++.h>
using namespace std;
//returning inversion count
int get_Icount(int arr[],int n){
   multiset<int> set1;
   set1.insert(arr[0]);
   int invcount = 0; //initializing result
   multiset<int>::iterator itset1;
   for (int i=1; i<n; i++){
      set1.insert(arr[i]);
      itset1 = set1.upper_bound(arr[i]);
      invcount += distance(itset1, set1.end());
   }
   return invcount;
}
int main()
{
   int arr[] = {8, 4, 2, 1};
   int n = sizeof(arr)/sizeof(int);
   cout << "Number of inversions count are : "<< get_Icount(arr,n);
   return 0;
}

出力

Number of inversions count are : 6

  1. マージソートを使用して配列内の反転をカウントするC/C ++プログラム？

    指定された配列をソートするために発生する反転の数は、反転数と呼ばれます。反転問題は、マージソートアルゴリズムを使用して解決できる古典的な問題です。この問題では、v左側にある要素よりも多くのすべての要素をカウントし、そのカウントを出力に追加します。 ThisLogicは、マージソートのマージ関数内で実行されます。 トピックをよりよく理解するために、例を見てみましょう。マージプロセスに関係する2つのサブアレイについて考えてみましょう- Input: arr[] = { 1, 9, 6, 4, 5} Output: Inversion count is 5 説明

  2. C++の平面内の平行四辺形の数

    平行四辺形を形成する点を含む平面が与えられます。タスクは、与えられた点を使用して形成できる平行四辺形の数を計算することです。平行四辺形では、四辺形の反対側は平行であるため、反対の角度は等しくなります。 入力 − int a[] = {0, 2, 5, 5, 2, 5, 2, 5, 2} Int b[] = {0, 0, 1, 4, 3, 8, 7, 11, 10} 出力 −平面内の平行四辺形の数− 3 説明 −（x、y）点が与えられ、これらの点を使用して、図に示すように3つの平行四辺形のカウントを形成できます。 入力 − a[] = {0, 3, 1, 4, 1, 5} b