পাইথনে একটি তালিকাকে একটি পূর্ণসংখ্যাতে কমাতে ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। যেকোন দুটি সংখ্যা নিয়ে আমরা সংখ্যার দৈর্ঘ্য কমাতে পারি, তাদের সরিয়ে দিতে পারি এবং শেষে তাদের যোগফল যোগ করতে পারি। এই ক্রিয়াকলাপটি করার খরচ হল দুটি পূর্ণসংখ্যার যোগফল যা আমরা সরিয়ে দিয়েছি। সংখ্যাগুলিকে একটি পূর্ণসংখ্যাতে হ্রাস করার সর্বনিম্ন মোট খরচ আমাদের খুঁজে বের করতে হবে৷

সুতরাং, ইনপুট যদি 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.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সংখ্যায় উপস্থিত উপাদান ব্যবহার করে একটি গাদা তৈরি করুন
• উত্তর :=0
• সংখ্যার আকার>=2, কর
  • a :=হিপ সংখ্যার শীর্ষস্থানীয় উপাদান
  • b :=হিপ সংখ্যার শীর্ষস্থানীয় উপাদান
  • উত্তর :=ans + a + b
  • হিপ সংখ্যায় 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