C++でブロックを構築するための最小時間

ブロックのリストがあると仮定します。blocks[i]=tの場合、これは、i番目のブロックを構築するのにt単位の時間が必要であることを意味します。ブロックは、1人のワーカーのみが作成できます。 1人の労働者は、2人の労働者に分割するか、ブロックを作成して家に帰ることができます。これらの2つの決定には時間がかかります。 1人のワーカーを2人のワーカーに分割する時間コストは、splitと呼ばれる数値として示されます。

したがって、入力がブロック=[1,2]で、split =5の場合、ワーカーを5つの時間単位で2つのワーカーに分割し、それぞれをブロックに割り当てることができるため、出力は7になります。 5+最大1および2=7です。

これを解決するには、次の手順に従います-

• 1つの優先キューpqを定義する

• 初期化i：=0の場合、i <ブロックのサイズの場合、更新（iを1増やします）、実行-

  • ブロック[i]をpqに挿入

• pq> 1のサイズで、実行-

  • pqから要素を削除する

  • x：=pqの最上位要素

  • pqから要素を削除する

  • split+xをpqに挿入します

• pqの最上位要素を返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minBuildTime(vector<int>& blocks, int split) {
      priority_queue<int, vector<int>, greater<int> > pq;
      for (int i = 0; i < blocks.size(); i++)
      pq.push(blocks[i]);
      while (pq.size() > 1) {
         pq.pop();
         int x = pq.top();
         pq.pop();
         pq.push(split + x);
      }
      return pq.top();
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2};
   cout << (ob.minBuildTime(v, 5));
}

入力

{1,2}, 5

出力

7