从C ++中给定的对象数组中找到最大高度金字塔

假设我们有一个n个对象的数组。每个对象的宽度为W [i]。我们必须以金字塔形的方式排列它们-

• ith的总宽度小于（i + 1）th

• 第ith个对象的总数小于第（i +1）个

例如，如果权重为[40，100，20，30]，则输出将为2。因此，最高级别为30，然后较低级别为20、40和100

为了解决这个问题，我们将使用贪婪方法。这个想法是使用将宽度较小的对象放在顶部，将下一个对象放在下面的级别，依此类推。要获得最大级别，请对给定的数组进行排序，然后尝试从上到下形成金字塔。

然后，在排序后找到数组的最小元素（如数组的第一个元素），将其放在顶部。然后尝试在其下构建具有更多对象和更大宽度的层。

示例

#include <iostream>
#include <algorithm>
using namespace std;
int maxLevelPyramid(int objects[], int n) {
   sort(objects, objects + n);
   int ans = 1;
   int prev_w = objects[0];
   int count_p = 1;
   int count_c = 0;
   int curr_w = 0;
   for (int i=1; i<n; i++){
      curr_w += objects[i];
      count_c++;
      if (curr_w > prev_w && count_c > count_p){
         prev_w = curr_w;
         count_p = count_c;
         count_c = curr_w = 0;
         ans++;
      }
   }
   return ans;
}
int main() {
   int boxes[] = {40, 100, 20, 30};
   int n = sizeof(boxes)/sizeof(boxes[0]);
   cout << "Max level of pyramid: " << maxLevelPyramid(boxes, n);
}

输出结果

Max level of pyramid: 2