Thời gian tối thiểu xây dựng khối trong C++

Giả sử chúng ta có danh sách các khối, nếu blocks[i] = t, nghĩa là khối thứ i cần t đơn vị thời gian để xây dựng. Một khối chỉ có thể được xây dựng bởi đúng một công nhân. Công nhân đơn lẻ có thể chia thành hai công nhân hoặc xây một khối thì về nhà. Hai quyết định này tốn một số thời gian. Chi phí thời gian chia một công nhân thành hai được cho là một số gọi là split.

Vì vậy, nếu đầu vào là blocks = [1,2], và split = 5, đầ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 cho một khối nên chi phí là 5 + max của 1 và 2 = 7.

Để giải quyết, chúng ta sẽ làm theo các bước:

• Định nghĩa hàng đợi ưu tiên pq

• Khởi tạo i := 0, khi i < kích thước blocks, cập nhật (tăng i lên 1), làm:

  • Chèn blocks[i] vào pq

• Khi kích thước pq > 1, làm:

  • Xóa phần tử từ pq

  • x := phần tử đầu pq

  • Xóa phần tử từ pq

  • Chèn split + x vào pq

• Trả về phần tử đầu pq

Hãy xem 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