숫자와 비용이라는 두 개의 숫자 목록이 있다고 가정합니다. 이제 비용 비용[i]에 대해 nums[i]를 늘리거나 줄일 수 있는 작업이 있다고 가정합니다. 우리는 이러한 연산을 얼마든지 수행할 수 있으며 모든 요소를 숫자로 동일하게 만들고 싶습니다. 필요한 최소 총 비용을 찾아야 합니다.
따라서 입력이 nums =[3, 2, 4] 비용 =[1, 10, 2]와 같으면 출력은 5가 됩니다. 마치 비용 1에 대해 숫자 3을 2로 줄일 수 있는 것과 같습니다. 그런 다음 각각 2의 비용으로 4를 두 번 감소시킬 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
helper() 함수를 정의합니다. 대상이 됩니다.
-
총계 :=0
-
enumerate(nums)의 각 i,n에 대해 수행
-
target이 n과 같지 않으면
-
총계 :=총계 + |n-대상| * 비용[i]
-
-
-
총 반환
-
기본 방법에서 다음을 수행합니다.
-
낮음 :=0, 높음 :=최대 숫자
-
낮음 <높음은 0이 아닌 동안 수행
-
중간 :=(낮음 + 높음) / 2
-
도우미(mid) <도우미(mid+1)이면
-
높음 :=중간
-
-
그렇지 않으면
-
낮음 :=중간 + 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