i번째 요소가 nums[i]개의 공을 포함하는 가방을 나타내는 배열 nums가 있다고 가정합니다. mx라는 다른 값도 있습니다. 다음 작업을 최대 mx번 수행할 수 있습니다. -
-
공이 든 가방을 선택하고 적어도 하나의 공이 포함된 두 개의 새 가방으로 나눕니다.
-
여기서 페널티는 가방에 넣을 수 있는 최대 공 수입니다.
수술 후 불이익을 최소화해야 합니다. 따라서 마지막으로 작업을 수행한 후 가능한 최소 페널티를 찾아야 합니다.
따라서 입력이 nums =[4,8,16,4], mx =4와 같으면 다음 작업을 수행할 수 있으므로 출력은 4가 됩니다. 처음에는 [4,8,16,4]와 같은 가방이 있습니다. , [4,8,8,8,4]와 같이 16개의 공이 있는 백을 분할한 다음 8개의 공이 있는 각 백에 대해 각각 4개의 공이 있는 두 개의 백으로 나누므로 배열은 [4,4,4, 8,8,4], 그 다음 [4,4,4,4,4,8,4] 그리고 마지막으로 [4,4,4,4,4,4,4,4], 따라서 여기에 최소 4개의 공이 있습니다. , 그것이 패널티입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
helper() 함수를 정의합니다. 이것은 대상이 됩니다. mx
-
target이 0과 같으면
-
mx + 1을 반환
-
-
개수 :=0
-
숫자의 각 숫자에 대해 수행
-
count :=count + (num - 1)/target의 몫
-
-
반환 횟수 <=mx
-
기본 방법에서 다음을 수행하십시오.
-
왼쪽 :=(nums의 모든 요소의 합 /(nums의 크기 + mx)) 및 1의 몫의 최대값
-
오른쪽 :=최대 숫자
-
왼쪽 <오른쪽, 하는 동안
-
mid :=(왼쪽 + 오른쪽)/2의 몫
-
helper(mid, mx)가 0이 아니면
-
오른쪽 :=중간
-
-
그렇지 않으면
-
왼쪽 :=중간 + 1
-
-
-
왼쪽으로 돌아가기
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def helper(target, mx): if target == 0: return mx + 1 count = 0 for num in nums: count += (num - 1) // target return count <= mx def solve(nums, mx): left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums) while left < right: mid = (left + right) // 2 if helper(mid, mx): right = mid else: left = mid + 1 return left nums = [4,8,16,4] mx = 4 print(solve(nums, mx))
입력
[4,8,16,4], 4
출력
4