สมมติว่าเรามีรายการบล็อก หากเรามีบล็อก[i] =t นี่หมายความว่าบล็อกที่ i ต้องใช้เวลา t หน่วยในการสร้าง บล็อกสามารถสร้างได้โดยคนงานเพียงคนเดียวเท่านั้น คนงานคนเดียวสามารถแบ่งออกเป็นสองคนหรือสร้างบล็อกแล้วกลับบ้าน การตัดสินใจทั้งสองนี้ใช้เวลาพอสมควร ค่าใช้จ่ายในการแบ่งคนงานหนึ่งคนออกเป็นสองคนจะได้รับเป็นตัวเลขที่เรียกว่าการแบ่ง
ดังนั้นหากอินพุตเป็นเหมือนบล็อก =[1,2] และแยก =5 ผลลัพธ์จะเป็น 7 เนื่องจากเราสามารถแบ่งคนงานออกเป็น 2 คนใน 5 หน่วยเวลา จากนั้นกำหนดแต่ละรายการให้กับบล็อกดังนั้นต้นทุน คือ 5 + สูงสุด 1 และ 2 =7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดลำดับความสำคัญ pq หนึ่งคิว
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของบล็อก อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
แทรกบล็อค[i] ลงใน pq
-
-
ในขณะที่ขนาดของ pq> 1 ให้ทำ -
-
ลบองค์ประกอบออกจาก pq
-
x :=องค์ประกอบด้านบนของ pq
-
ลบองค์ประกอบออกจาก pq
-
แทรก split + x ลงใน pq
-
-
คืนค่าองค์ประกอบด้านบนของ pq
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
{1,2}, 5 ผลลัพธ์
7
