Сложность: hard
Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.
Выведите минимальное время, необходимое для строительства всех блоков.
Изначально есть только один рабочий.
Пример:
Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.
👨💻 Алгоритм:
1⃣Подготовка кучи строительного времени:
Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.
2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.
3⃣Возврат результата:
Когда в куче останется только одно значение, оно и будет минимальным временем, необходимым для строительства всех блоков.
😎 Решение:
#include <vector>
#include <queue>
class Solution {
public:
int minBuildTime(std::vector<int>& blocks, int split) {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq(blocks.begin(), blocks.end());
while (pq.size() > 1) {
int x = pq.top(); pq.pop();
int y = pq.top(); pq.pop();
pq.push(split + y);
}
return pq.top();
}
};
Ставь 👍 и забирай 📚 Базу знаний