给出一列数以及每个位置增/减1需要的cost,问最少多少cost可以让整列数变成一样的。因为最后相同的数必定在原数列最小值和最大值之间,而且总cost会是个U型曲线,所以二分结果找最小值
参考了Discussion -> https://leetcode.com/problems/minimum-cost-to-make-array-equal/solutions/3663660/binary-search-video-java-c-python/
1 #2448
2 #Runtime: 748 ms (Beats 42.86%)
3 #Memory: 24.8 MB (Beats 71.43%)
4
5 class Solution(object):
6 def minCost(self, nums, cost):
7 """
8 :type nums: List[int]
9 :type cost: List[int]
10 :rtype: int
11 """
12 def cal(m):
13 t = 0
14 for i in range(len(nums)):
15 t += abs(nums[i] - m) * cost[i]
16 return t
17
18 l, r = nums[0], nums[0]
19 for i in nums:
20 l = min(l, i)
21 r = max(r, i)
22 print(l)
23 print(r)
24 ans = 0
25 while l < r:
26 mid = (l + r) // 2
27 cost1 = cal(mid)
28 cost2 = cal(mid + 1)
29 if cost1 > cost2:
30 l = mid + 1
31 ans = cost2
32 else:
33 r = mid
34 ans = cost1
35 return ans