ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যা দৈর্ঘ্যের কিছু স্টিক আছে। X এবং Y দৈর্ঘ্যের যেকোন দুটি স্টিককে X + Y মূল্য দিয়ে একটি লাঠিতে সংযোগ করতে পারি। একটি লাঠি অবশিষ্ট না থাকা পর্যন্ত এটি করা হবে। আমাদের এইভাবে একটি লাঠিতে সমস্ত প্রদত্ত লাঠি সংযুক্ত করার ন্যূনতম খরচ খুঁজে বের করতে হবে। সুতরাং স্ট্যাক যদি [2,4,3] হয়, তাহলে আউটপুট হবে 14।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি সর্বাধিক হিপ অগ্রাধিকার সারি pq সংজ্ঞায়িত করুন
- s-এর সমস্ত উপাদান pq-তে প্রবেশ করান
- উত্তর :=0
- যদিও pq এর একাধিক উপাদান আছে
- temp :=সারির শীর্ষে, pq থেকে শীর্ষ মুছে দিন
- temp :=temp + pq এর শীর্ষ উপাদান, এবং pq থেকে মুছে দিন
- উত্তর :=ans + temp
- pq-এ temp সন্নিবেশ করান
- উত্তর ফেরত দিন
উদাহরণ(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]
আউটপুট
14
