파이썬에서 가장 작은 그룹의 가능한 최대값을 찾는 프로그램

<시간/>

nums라는 숫자 목록과 또 다른 값 k가 있다고 가정합니다. 목록을 k개의 연속된 그룹으로 분할해야 합니다. 가장 작은 그룹은 모든 그룹 중에서 합이 가장 작은 그룹입니다. 따라서 가장 작은 그룹의 가능한 최대값을 찾으십시오.

따라서 입력이 nums =[2, 6, 4, 5, 8] k =3과 같으면 목록을 [2, 6], [4와 같은 세 그룹으로 나눌 수 있으므로 출력은 8이 됩니다. , 5], [8]. 따라서 최소 그룹의 합계는 8입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

is_divisible() 함수를 정의합니다. 대상이 됩니다.
대상 <=1이면
- 참을 반환
num_chunks :=0, current_sum :=0
숫자의 각 x에 대해 수행
- current_sum :=current_sum + x
- current_sum>=target이면
  - current_sum :=0
  - num_chunks :=num_chunks + 1
  - num_chunks가 k와 같으면
    - 참을 반환
거짓을 반환
주요 방법에서 다음을 수행하십시오 -
왼쪽 :=1
right :=(모든 요소의 합) / k + 1
왼쪽 <오른쪽 - 1 동안 수행
- 중간 :=(왼쪽 + 오른쪽) / 2
- is_divisible(mid)이 참이면
  - 왼쪽 :=중간
- 그렇지 않으면
  - 오른쪽 :=중간
왼쪽으로 돌아가기

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, nums, k):
      def is_divisible(target):
         if target <= 1:
            return True
         num_chunks = 0
         current_sum = 0
         for x in nums:
            current_sum += x
            if current_sum >= target:
               current_sum = 0
               num_chunks += 1
               if num_chunks == k:
                  return True
         return False
      left = 1
      right = sum(nums) // k + 1
      while left < right - 1:
         mid = (left + right) // 2
         if is_divisible(mid):
            left = mid
         else:
            right = mid
      return left
ob = Solution()
nums = [2, 6, 4, 5, 8]
k = 3
print(ob.solve(nums, k))

입력

[2, 6, 4, 5, 8], 3