在C ++中使用给定的线段长度可以制作的最大平行四边形数量

  • Z时代
  • 2024-01-10
  • 分类：综合

给定任务是，如果每个线段最多可以在一个平行四边形中使用，则查找使用给定N个线段可以制作的平行四边形的最大数量。

现在让我们使用示例了解我们必须做的事情-

输入− Arr [] = {8，3，1，3，8，7，1，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 <N并检查（Arr [i]> L），然后在if语句中放入L = Arr [i]。在循环外部，将L的大小增加1。

  • 然后初始化频率数组int Freq [L] = {0}。从i = 0循环直到i <N，并将每个分段的出现次数增加1。

  • int类型的初始化计数= 0，用于存储平行四边形的最终计数。

  • 从i = 0循环直到i <L，并检查可以用4个相似边制成的平行四边形，如果找到，则相应地增加count的值。

  • 初始化类型为int的left = 0以存储可以使用2个相似边形成的平行四边形的数量。

  • 最后从i = 0循环直到i <L，然后检查if（Freq [i]> = 2），如果是，则在左边加1。

  • 将count + = left / 2并返回count。

示例

#include <bits/stdc++.h>
using namespace std;
int MaxParr(int N, int Arr[]){
   //查找频率数组的长度
   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++){
      //每个线段的出现次数增加
      Freq[Arr[i]] += 1;
   }
   //要存储平行四边形的数量
   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++){
      //计算剩余2个或更多事件的细分
      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

以上是 在C ++中使用给定的线段长度可以制作的最大平行四边形数量 的全部内容， 来源链接： utcz.com/z/334944.html

回到顶部