ধরুন আমাদের কাছে ব্লকের একটি তালিকা আছে, যদি আমাদের ব্লক[i] =t থাকে, তাহলে এর মানে হল i-th ব্লকের টি ইউনিট তৈরি করতে সময় লাগবে। একটি ব্লক শুধুমাত্র একজন শ্রমিক দ্বারা তৈরি করা যেতে পারে। একক কর্মী হয় দুই কর্মীতে বিভক্ত হতে পারে অথবা একটি ব্লক তৈরি করে বাড়ি যেতে পারে। এই দুটি সিদ্ধান্ত কিছুটা সময় নেয়। একজন কর্মীকে দুই শ্রমিকে বিভক্ত করার সময় ব্যয়কে বিভক্ত বলে একটি সংখ্যা হিসাবে দেওয়া হয়।
সুতরাং, যদি ইনপুটটি ব্লক =[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
-এ split + 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
