数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中构建块的最小时间
假设我们有一列块，如果我们有 blocks[i] = t，这意味着第 i 个块需要 t 个单位时间才能构建。一个块只能由一个工人构建。单个工人可以分成两个工人，或者构建一个块然后回家。这两个决定都需要一些时间。将一个工人分成两个工人的时间成本由一个名为 split 的数字给出。
因此，如果输入像 blocks = [1,2]，并且 split = 5，则输出将为 7，因为我们可以在 5 个时间单位内将工人分成 2 个工人，然后将每个工人分配到一个块，所以成本为 5 + 1 和 2 的最大值 = 7。
为了解决这个问题，我们将遵循以下步骤：
定义一个优先级队列 pq
对于初始化 i := 0，当 i < blocks 的大小，更新（i 增加 1），执行：
将 blocks[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
更新于：2020年7月11日
124 次浏览
广告