資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告