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