python에서 k일 동안 스카이다이버에게 필요한 최소 우주선을 찾는 프로그램

<시간/>

각 값이 함께 스카이다이빙하려는 사람들의 그룹을 나타내는 nums라는 숫자 목록이 있다고 가정합니다. 그리고 스카이다이빙을 신청할 수 있는 날을 나타내는 또 다른 값 k가 있습니다. 우리는 k일 이내에 모든 요청을 이행할 수 있는 데 필요한 비행기의 최소 수용 인원을 찾아야 합니다. 요청은 주어진 순서대로 이행되어야 하며 비행기는 하루에 한 번만 비행할 수 있습니다.

따라서 입력이 nums =[16, 12, 18, 11, 13], k =3과 같으면 출력은 28이 됩니다. 28인 비행기는 주어진 요청을 [16, 12], [ 18], [11, 13].

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

nums가 비어 있으면
- 0을 반환
start :=nums의 최대값, end :=nums의 모든 요소의 합
시작하는 동안 <끝, 수행
- 중간 :=(시작 + 끝) / 2
- 일 :=1, 온도 :=0
- 숫자 단위의 각 숫자에 대해 다음을 수행합니다.
  - temp + num> mid이면
    - 일 :=일 + 1
    - temp :=숫자
  - 그렇지 않으면
    - temp :=온도 + 숫자
- 만일> k이면
  - 시작 :=중간 + 1
- 그렇지 않으면
  - 끝 :=중간
리턴 시작

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

예시

class Solution:
   def solve(self, nums, k):
      if not nums:
         return 0

      start, end = max(nums), sum(nums)

      while start < end:
         mid = (start + end) // 2

         days = 1
         temp = 0
         for num in nums:
            if temp + num > mid:
               days += 1
               temp = num
            else:
               temp += num

         if days > k:
            start = mid + 1
         else:
            end = mid

      return start

ob = Solution()
nums = [16, 12, 18, 11, 13]
k = 3
print(ob.solve(nums, k))

입력

[16, 12, 18, 11, 13], 3