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

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

इसलिए, यदि इनपुट संख्या =[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.

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

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

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

उदाहरण

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