C++で指定された長さの線分を使用して作成できる平行四辺形の最大数

与えられたタスクは、各線分が最大で1つの平行四辺形で使用できる場合に、指定されたN個の線分を使用して作成できる平行四辺形の最大数を見つけることです。

例を使用して、私たちがしなければならないことを理解しましょう-

入力 − arr [] ={8、3、1、3、8、7、1、3、5、3}

出力 − 2

説明 −上記の線分で、形成できる2つの平行四辺形は、それぞれ辺8、1、8、1および3、3、3、3です。

入力 − arr [] ={7、9、9、7}

出力 − 1

以下のプログラムで使用されるアプローチは次のとおりです

• 作成できる平行四辺形の最大数は、=4つの等しいまたは類似した辺で作成できる平行四辺形と、2つの類似した辺を使用して作成できる平行四辺形です。

• 関数MaxParr（）で、変数L =Arr [0]を初期化します。これは、線分の頻度を格納するために使用される配列のサイズとして使用されます。

• i =1からi L）かどうかを確認し、ifステートメント内にL =Arr[i]を入力します。ループの外側では、Lのサイズを1増やします。

• 次に、周波数配列int Freq [L]={0}を初期化します。 i =0からi

• 平行四辺形の最終カウントを格納するint型の初期化カウント=0。

• i =0からi

• int型のleft=0を初期化して、2つの類似した辺を使用して形成できる平行四辺形の数を格納します。

• 最後に、i =0からi =2）かどうかを確認し、そうであれば、左に1を追加します。

• count + =left/2を入れてcountを返します。

例

#include <bits/stdc++.h>
using namespace std;
int MaxParr(int N, int Arr[]){
   //Finding length of frequency array
   int L = Arr[0];
   for (int i = 1; i < N; i++){
      if (Arr[i] > L)
         L = Arr[i];
   }
   L = L + 1;
   int Freq[L] = {0};
   for (int i = 0; i < N; i++){
      //Increasing occurrence of each line segment
      Freq[Arr[i]] += 1;
   }
   // To store the number of parallelograms
   int count = 0;
   for (int i = 0; i < L; i++){
      /*parallelograms that can be made using 4 same sides*/
      count += int(Freq[i] / 4);
      Freq[i] = Freq[i] % 4;
   }
   int left = 0;
   for (int i = 0; i < L; i++){
      //Counting segments with 2 or more occurrences left
      if (Freq[i] >= 2)
         left += 1;
   }
   /*Adding parallelograms that can be formed using using 2 similar sides into the final count*/
   count += left / 2;
   return count;
}
int main(){
   int N = 10;
   int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3};
   cout<< MaxParr(N, Arr);
}

出力

上記のコードを実行すると、次の出力が得られます-

2