Giả sử chúng ta có một danh sách các khối, nếu chúng ta có các khối [i] =t, điều này có nghĩa là khối thứ i cần t đơn vị thời gian để được xây dựng. Một khối chỉ có thể được xây dựng bởi chính xác một công nhân. Một công nhân có thể tách thành hai công nhân hoặc xây một khối sau đó về nhà. Hai quyết định này cần một thời gian. Chi phí thời gian để tách một công nhân thành hai công nhân được cho dưới dạng một số được gọi là phân chia.
Vì vậy, nếu đầu vào giống như các khối =[1,2] và split =5, thì đầu ra sẽ là 7 vì chúng ta có thể chia công nhân thành 2 công nhân trong 5 đơn vị thời gian sau đó gán mỗi người trong số họ vào một khối nên chi phí là 5 + tối đa là 1 và 2 =7.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
xác định một hàng đợi ưu tiên pq
-
để khởi tạo i:=0, khi tôi
-
chèn khối [i] vào pq
-
-
trong khi kích thước của pq> 1, do -
-
xóa phần tử khỏi pq
-
x:=phần tử hàng đầu của pq
-
xóa phần tử khỏi pq
-
chèn split + x vào pq
-
-
trả về phần tử hàng đầu của pq
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{1,2}, 5 Đầu ra
7