สมมติว่าเรามีรายการบล็อก ถ้า blocks[i] = t หมายความว่า บล็อกที่ i ต้องใช้เวลา t หน่วยในการสร้าง บล็อกสามารถสร้างได้โดยพนักงานเพียงคนเดียวเท่านั้น พนักงานคนเดียวสามารถแยกเป็นสองคนได้ หรือสร้างบล็อกแล้วกลับบ้าน สองการตัดสินใจนี้ใช้เวลา เวลาในการแยกพนักงานหนึ่งคนเป็นสองคน กำหนดเป็นตัวเลขที่ชื่อว่า split
ดังนั้น หากอินพุทคือ blocks = [1,2], และ split = 5 ผลลัพธ์จะเป็น 7 เนื่องจากเราสามารถแยกพนักงานเป็น 2 คนใน 5 หน่วยเวลา แล้วมอบให้แต่ละคนสร้างบล็อกหนึ่งบล็อก ดังนั้นค่าใช้จ่ายคือ 5 + max(1, 2) = 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
กำหนด priority queue pq (min-heap)
for i := 0 ถึงขนาดของ blocks - 1: ใส่ blocks[i] ลง pq
while ขนาดของ pq > 1:
ลบองค์ประกอบออกจาก pq (ค่าน้อยสุด)
x := องค์ประกอบบนสุดของ pq
ลบองค์ประกอบออกจาก pq
ใส่ split + x ลง pq
คืนค่าองค์ประกอบบนสุดของ pq
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minBuildTime(vector& blocks, int split) {
priority_queue, greater> 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();
}
};
int main() {
Solution ob;
vector v = {1, 2};
cout << (ob.minBuildTime(v, 5));
return 0;
}
อินพุต
{1,2}, 5
เอาต์พุต
7
