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

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

যদি ইনপুট হয় nums = [2, 3, 4, 5, 6], তবে আউটপুট হবে ৪৫, কারণ: ২ ও ৩ নিয়ে মুছে ফেললে [4, 5, 6, 5], তারপর ৪ ও ৫ নিয়ে [6, 5, 9], তারপর ৬ ও ৫ নিয়ে [9, 11], অবশেষে ৯ ও ১১ নিয়ে ১৯। মোট খরচ ৪৫।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

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]