文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

你是個(gè)城市規(guī)劃工作者，手里負(fù)責(zé)管轄一系列的街區(qū)。在這個(gè)街區(qū)列表中 blocks[i] = t 意味著第 i 個(gè)街區(qū)需要 t 個(gè)單位的時(shí)間來(lái)建造。

由于一個(gè)街區(qū)只能由一個(gè)工人來(lái)完成建造。

所以，一個(gè)工人要么需要再召喚一個(gè)工人（工人數(shù)增加 1）；要么建造完一個(gè)街區(qū)后回家。這兩個(gè)決定都需要花費(fèi)一定的時(shí)間。

一個(gè)工人再召喚一個(gè)工人所花費(fèi)的時(shí)間由整數(shù) split 給出。

注意：如果兩個(gè)工人同時(shí)召喚別的工人，那么他們的行為是并行的，所以時(shí)間花費(fèi)仍然是 split。

最開(kāi)始的時(shí)候只有 一個(gè) 工人，請(qǐng)你最后輸出建造完所有街區(qū)所需要的最少時(shí)間。

示例 1： 輸入：blocks = [1], split = 1 輸出：1 解釋：我們使用 1 個(gè)工人在 1 個(gè)時(shí)間單位內(nèi)來(lái)建完 1 個(gè)街區(qū)。示例 2： 輸入：blocks = [1,2], split = 5 輸出：7 解釋：我們用 5 個(gè)時(shí)間單位將這個(gè)工人分裂為 2 個(gè)工人， 然后指派每個(gè)工人分別去建造街區(qū)，從而時(shí)間花費(fèi)為 5 + max(1, 2) = 7示例 3： 輸入：blocks = [1,2,3], split = 1 輸出：4 解釋： 將 1 個(gè)工人分裂為 2 個(gè)工人，然后指派第一個(gè)工人去建造最后一個(gè)街區(qū)， 并將第二個(gè)工人分裂為 2 個(gè)工人。 然后，用這兩個(gè)未分派的工人分別去建造前兩個(gè)街區(qū)。 時(shí)間花費(fèi)為 1 + max(3, 1 + max(1, 2)) = 4提示： 1 <= blocks.length <= 1000 1 <= blocks[i] <= 10^5 1 <= split <= 100

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-time-to-build-blocks
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

貪心算法（Greedy Algorithm）之霍夫曼編碼

• 類似霍夫曼樹，將最小的兩個(gè)合并，再放回優(yōu)先隊(duì)列，使得數(shù)量大的被加的次數(shù)少

class Solution { public:int minBuildTime(vector<int>& blocks, int split) {priority_queue<int, vector<int>, greater<int>> q;//小頂堆for(int b : blocks) q.push(b);while(q.size() > 1){int a = q.top();q.pop();int b = q.top();q.pop();q.push(max(a,b)+split);}return q.top();} };

68 ms 9.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1199. 建造街区的最短时间（优先队列贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。