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

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

উদাহরণস্বরূপ, nums = [3, 2, 4], costs = [1, 10, 2] হলে আউটপুট হবে 5, কারণ 3 কে 2-তে কমাতে খরচ 1, তারপর 4 কে দুবার কমাতে খরচ ২x২=৪, মোট ৫।

সমাধানের ধাপসমূহ

helper() ফাংশন সংজ্ঞায়িত করুন যা target নেয়
total := 0
প্রতিটি i,nenumerate(nums)-এর জন্য,
- যদি target != n, তবে
  - total := total + |n-target| * costs[i]
total ফেরত দিন

মূল মেথড থেকে:

low := 0, high := nums-এর সর্বোচ্চ
যখন low < high,
- mid := (low + high) / 2
- যদি helper(mid) < helper(mid+1), তবে
  - high := mid
- অন্যথায়,
  - low := mid + 1
helper(low) ফেরত দিন

উদাহরণ

class Solution:
    def solve(self, nums, costs):
        def helper(target):
            total = 0
            for i,n in enumerate(nums):
                if target != n:
                    total += abs(n-target) * costs[i]
            return total
        low,high = 0, max(nums)
        while low < high:
            mid = low + high >> 1
            if helper(mid) < helper(mid+1):
                high = mid
            else:
                low = mid + 1
        return helper(low)

ob = Solution()
nums = [3, 2, 4]
costs = [1, 10, 2]
print(ob.solve(nums, costs))

ইনপুট

[3, 2, 4], [1, 10, 2]