Python程序：查找使列表元素相等所需的最小总成本

假设我们有两个数字列表，分别称为 nums 和 costs。现在考虑，有一个操作可以将 nums[i] 增加或减少，成本为 costs[i]。我们可以执行任意数量的此类操作，并且我们希望使 nums 中的所有元素都相等。我们必须找到所需的最小总成本。

因此，如果输入类似于 nums = [3, 2, 4] costs = [1, 10, 2]，则输出将为 5，因为我们可以将数字 3 减少到 2，成本为 1。然后我们可以将 4 递减两次，每次成本为 2。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数 helper()。这将接收目标值。

  • total := 0

  • 对于每个 i,n 在 enumerate(nums) 中，执行以下操作：

    • 如果目标与 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]

输出

5

更新于： 2020-10-07

224 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告