โปรแกรมหาต้นทุนรวมต่ำสุดเพื่อทำให้องค์ประกอบในรายการเท่ากันใน Python

สมมติว่ามีรายการตัวเลขสองรายการชื่อ nums และ costs พิจารณาการดำเนินการที่เราสามารถเพิ่มหรือลด nums[i] ด้วยต้นทุน costs[i] เราสามารถดำเนินการได้ไม่จำกัดครั้ง และต้องการให้ทุกองค์ประกอบใน nums เท่ากัน เราต้องหาต้นทุนรวมต่ำสุดที่จำเป็น

เช่น ถ้าอินพุตคือ nums = [3, 2, 4] costs = [1, 10, 2] ผลลัพธ์จะเป็น 5 เนื่องจากเราสามารถลด 3 เหลือ 2 ด้วยต้นทุน 1 แล้วลด 4 สองครั้ง ต้นทุน 2 ต่อครั้ง

ขั้นตอนการแก้ปัญหา

• กำหนดฟังก์ชัน helper() รับ target
  • total := 0
  • สำหรับแต่ละ i, n ใน enumerate(nums) ทำ
    • ถ้า target ไม่เท่ากับ n แล้ว total := total + |n-target| * costs[i]
  • คืนค่า total
• จากเมธอดหลัก
  • low := 0, high := ค่าสูงสุดของ nums
  • while 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]

  เอาต์พุต

  5