সি++-এ ব্লক তৈরি করার ন্যূনতম সময়

ধরা যাক blocks নামে একটি লিস্ট আছে, যদি blocks[i] = t হয়, এর মানে i-তম ব্লক তৈরি করতে t यুনিট সময় লাগবে। একটি ব্লক শুধু একজন ওয়ার্কারের দ্বারা তৈরি হতে পারে। একক ওয়ার্কার হয় দুই ওয়ার্কারে ভাগ হতে পারে অথবা একটি ব্লক বানাতে পারে তারপর বাড়ি ফেরতে পারে। এই দুটি সিদ্ধান্ত কিছু সময় নেয়। একটি ওয়ার্কারকে দুজন ওয়ার্কারে ভাগ করার সময় খরচ split নামের একটি সংখ্যা হিসেবে দেওয়া আছে।

তাই, যদি ইনপুট blocks = [1,2], এবং split = 5 হয়, তবে আউটপুট হবে 7 কারণ আমরা ৫ টাইম ইউনিটে ওয়ার্কারকে ২ জনে ভাগ করতে পারি তারপর তাদের প্রতিটি ব্লকে অ্যাসাইন করি তাই খরচ 5 + 1 এবং 2-এর ম্যাক্সিমাম = 7।

এটি সমাধান করতে, আমরা নিচের ধাপগুলো অনুসরণ করব -

একটি প্রায়োরিটি কিউ pq ডিফাইন করুন
i := 0 থেকে শুরু করুন, যখন i < blocks-এর আকার, (i ১ করে বাড়ান), করুন -
- blocks[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