在Python中查找均衡列表元素的最小总成本的程序
假设我们有两个数字列表,分别称为nums和cost。现在考虑,存在一个可以增加或减少成本[i]的nums[i]的操作。我们可以执行任意数量的这些操作,并且希望使所有元素在num中相等。我们必须找到所需的最低总成本。
因此,如果输入像nums=[3,2,4]cost=[1,10,2],那么输出将是5,就好像我们可以将1的成本将3减少为2一样。我们可以减少4次两次,每次费用为2。
为了解决这个问题,我们将遵循以下步骤-
定义一个功能helper()。这将成为目标
总计:=0
对于inumerate(nums)中的每个i,n,执行
总数:=总数+|n-target|*费用[i]
如果目标与n不同,则
总回报
在主要方法中,执行以下操作:
低:=0,高:=最大值
当低<高不为零时,
低:=中+1
高:=中
中:=(低+高)/2
如果helper(mid)<helper(mid+1),则
除此以外,
返回助手(低)
让我们看下面的实现以更好地理解-
示例
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