मान लीजिए कि हमारे पास धनात्मक पूर्णांक लंबाई वाली कुछ छड़ें हैं। हम X और Y लंबाई की किन्हीं भी दो छड़ियों को X + Y की लागत देकर एक छड़ी में जोड़ सकते हैं। यह तब तक किया जाएगा जब तक कि एक छड़ी शेष न हो। हमें इस प्रकार दी गई सभी छड़ियों को एक छड़ी में जोड़ने की न्यूनतम लागत ज्ञात करनी है। तो अगर स्टैक [2,4,3] है, तो आउटपुट 14 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- अधिकतम हीप प्राथमिकता कतार pq परिभाषित करें
- s के सभी तत्वों को pq में सम्मिलित करें
- उत्तर:=0
- जबकि pq में एक से अधिक तत्व हैं
- अस्थायी:=कतार में सबसे ऊपर, pq से शीर्ष हटाएं
- अस्थायी:=अस्थायी + pq का शीर्ष तत्व, और pq से हटाएं
- उत्तर:=उत्तर + अस्थायी
- pq में अस्थायी डालें
- वापसी उत्तर
उदाहरण(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