C++で指定されたオブジェクトの配列から最大の高さのピラミッドを見つけます

n個のオブジェクトの配列があるとします。各オブジェクトの幅はW[i]です。 -

• i番目の全幅が（i + 1）番目未満

• i番目のオブジェクトの総数が（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