給出一列數(shù)以及每個位置增/減1需要的cost，問最少多少cost可以讓整列數(shù)變成一樣的。因為最后相同的數(shù)必定在原數(shù)列最小值和最大值之間，而且總cost會是個U型曲線，所以二分結(jié)果找最小值
參考了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