C++-এ স্টিক কানেক্ট করার ন্যূনতম খরচ

মনে করুন কিছু স্টিক আছে যাদের দৈর্ঘ্য ধনাত্মক পূর্ণসংখ্যা। আমরা যেকোনো দুটি স্টিক `X` এবং `Y` দৈর্ঘ্যের কানেক্ট করে একটি স্টিক বানাতে পারি `X + Y` খরচ দিয়ে। এটি তখন পর্যন্ত চলবে যতক্ষণ না একটি স্টিক বাকি থাকে। দেওয়া সব স্টিকগুলো এক করার ন্যূনতম খরচ বের করতে হবে। যদি স্টিক হয় `[2,4,3]`, তবে আউটপুট হবে ১৪।

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

এক্স ম্যাক্স হিপ প্রায়োরিটি কিউ `pq` সংজ্ঞায়িত করুন
`s`-এর সব এলিমেন্ট `pq`-তে ইনসার্ট করুন
`ans := 0`
যখন `pq`-তে একটির অধিক এলিমেন্ট থাকে
- `temp := pq`-এর টপ, `pq`-থেকে টপ ডিলিট করুন
- `temp := temp + pq`-এর টপ এলিমেন্ট, এবং `pq`-থেকে ডিলিট করুন
- `ans := ans + temp`
- `temp`-কে `pq`-তে ইনসার্ট করুন
`ans` রিটার্ন করুন

উদাহরণ (C++)

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -

#include <bits/stdc++.h> using namespace std; class Solution { public:    int connectSticks(vector<int>& s) {       priority_queue <int, vector<int>, greater<int> > pq;       for(int i =0;i<s.size();i++)pq.push(s[i]);       int ans = 0;       while(pq.size()>1){          int temp = pq.top();          pq.pop();          temp += pq.top();          pq.pop();          ans+=temp;          pq.push(temp);       }       return ans;    } }; main(){    vector<int> v = {2,4,3};    Solution ob;    cout <<ob.connectSticks(v); }

ইনপুট

[2,4,3]