말뚝이라고 하는 숫자 목록과 k 값이 있다고 가정합니다. 말뚝[i]은 말뚝 i에 있는 돌의 수를 나타냅니다. 매 시간마다 우리는 아무 더미나 선택하고 그 더미에서 r개의 돌을 제거합니다. r개 미만의 돌이 있는 더미를 선택하면 더미를 치우는 데 여전히 1시간이 걸립니다. k 시간 이하의 모든 돌을 제거할 수 있도록 r의 최소값을 찾아야 합니다.
따라서 입력이 더미 =[3, 6, 4] k =5와 같다면 출력은 3이 됩니다. 왜냐하면 r =시간당 돌 3개의 경우 2시간 안에 두 번째 더미를 지울 수 있기 때문입니다. 2시간 안에 세 번째, 1시간 안에 첫 번째 더미를 치웁니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- l :=1
- h :=최대 더미
- r :=h
- turns() 함수를 정의합니다. 시간이 걸립니다
- 목록에 있는 모든 요소의 합계를 (더미의 각 b에 대해 b / r의 상한선)
- 기본 방법에서 다음을 수행합니다. -
- l
- mid :=(l + h) / 2의 바닥
- 회전(mid)> k이면
- l :=중간 + 1
- 그렇지 않으면
- h :=중간
- r :=r과 mid의 최소값
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from math import ceil def solve(piles, k): l = 1 h = max(piles) r = h def turns(r): return sum(ceil(b / r) for b in piles) while l < h: mid = (l + h) // 2 if turns(mid) > k: l = mid + 1 else: h = mid r = min(r, mid) return r piles = [3, 6, 4] k = 5 print(solve(piles, k))
입력
[3, 6, 4], 5
출력
3