मान लीजिए कि हमारे पास ब्लॉकों की एक सूची है, यदि हमारे पास ब्लॉक [i] =t है, तो इसका मतलब है कि i-th ब्लॉक को बनाने के लिए t यूनिट समय की आवश्यकता है। एक ब्लॉक केवल एक कार्यकर्ता द्वारा बनाया जा सकता है। एकल कार्यकर्ता या तो दो श्रमिकों में विभाजित हो सकता है या एक ब्लॉक का निर्माण कर सकता है फिर घर जा सकता है। इन दोनों फैसलों में कुछ समय लगता है। एक कार्यकर्ता को दो श्रमिकों में विभाजित करने की समय लागत को विभाजन नामक संख्या के रूप में दिया जाता है।
इसलिए, यदि इनपुट ब्लॉक =[1,2], और विभाजन =5 की तरह है, तो आउटपुट 7 होगा क्योंकि हम कार्यकर्ता को 5 समय इकाइयों में 2 श्रमिकों में विभाजित कर सकते हैं, फिर उनमें से प्रत्येक को एक ब्लॉक में आवंटित कर सकते हैं ताकि लागत 5 + अधिकतम 1 और 2 =7. है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक प्राथमिकता कतार pq परिभाषित करें
-
इनिशियलाइज़ i :=0 के लिए, जब i <ब्लॉक का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -
-
pq में ब्लॉक [i] डालें
-
-
जबकि pq> 1 का आकार, करें −
-
pq से तत्व हटाएं
-
x :=pq का शीर्ष अवयव
-
pq से तत्व हटाएं
-
pq में स्प्लिट + x डालें
-
-
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