C++에서 주어진 길이의 선분을 사용하여 만들 수 있는 평행사변형의 최대 수

각 선분을 하나의 평행사변형에서 최대로 사용할 수 있는 경우 주어진 N개의 선분을 사용하여 만들 수 있는 평행사변형의 최대 수를 찾는 작업이 주어집니다.

이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -

입력 - Arr[] ={8, 3, 1, 3, 8, 7, 1, 3, 5, 3}

출력 - 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
2개의 유사한 변을 사용하여 형성할 수 있는 평행사변형의 수를 저장하기 위해 int 유형의 left=0을 초기화합니다.
마지막으로 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);
}

출력

위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -