पायथन में सूची को एक पूर्णांक में कम करने की न्यूनतम लागत खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। हम किन्हीं दो संख्याओं को लेकर, उन्हें हटाकर, और उनके योग को अंत में जोड़कर nums की लंबाई कम कर सकते हैं। इस ऑपरेशन की लागत उन दो पूर्णांकों का योग है जिन्हें हमने हटाया। हमें nums को एक पूर्णांक में कम करने की न्यूनतम कुल लागत ढूंढनी है।

इसलिए, यदि इनपुट nums = [2, 3, 4, 5, 6] जैसा है, तो आउटपुट 45 होगा, क्योंकि हम 2 और 3 लेते हैं फिर हटाकर [4, 5, 6, 5] प्राप्त करते हैं, फिर हम 4 और 5 लेते हैं फिर हटाकर [6, 5, 9] प्राप्त करते हैं, फिर 6 और 5 लेते हैं, फिर उन्हें हटाते हैं और [9, 11] प्राप्त करते हैं, और अंत में 9 और 11 को हटाते हैं, हमें 19 मिलेगा। इसलिए योग 45 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

• nums में मौजूद तत्वों का उपयोग करके एक हीप बनाएं
• ans := 0
• जब तक nums का आकार >= 2, करें
  • a := हीप nums का शीर्ष तत्व
  • b := हीप nums का शीर्ष तत्व
  • ans := ans + a + b
  • a+b को हीप nums में डालें
• ans वापस करें

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

उदाहरण

class Solution:    def solve(self, nums):       import heapq       heapq.heapify(nums)       ans = 0       while len(nums) >= 2:          a = heapq.heappop(nums)          b = heapq.heappop(nums)          ans += a + b          heapq.heappush(nums, a + b)       return ans ob = Solution() nums = [2, 3, 4, 5, 6] print(ob.solve(nums))

इनपुट

[2, 3, 4, 5, 6]

आउटपुट

45