在C ++中构建模块的最短时间

假设我们有一个块列表，如果我们有blocks [i] = t，这意味着第i个块需要t单位时间来构建。一个街区只能由一个工人建造。单身工人可以分成两个工人，也可以建一个街区然后回家。这两个决定需要一些时间。将一个工人拆分为两个工人的时间成本称为“拆分”。

因此，如果输入像是blocks [[1,2]，并且split = 5，那么输出将是7，因为我们可以将worker分成5个时间单位的2个worker，然后将每个worker分配给一个block，因此成本是5 +最大值1和2 = 7。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个优先级队列pq

• 对于初始化i：= 0，当i <块大小时，更新（将i增加1），执行-

• 将块[i]插入pq

• 当pq> 1的大小时-

• 从pq中删除元素

• x：= pq的顶部元素

• 从pq中删除元素

• 将split + x插入pq

• 返回pq的top元素

让我们看下面的实现以更好地理解-

示例

#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