You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by a[i]. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum. You can only choose consecutive toffee packets to put in a box.
N,M <= 10^5. a[i] <= 10^3. Time Limit : 1s.
Input : 4 2 10 3 5 7
Output: 13
Explanation : Below are the possible assignments of toffee packets to boxes. 10 [3 5 7] 10 3 [5 7] 10 3 5 [7] For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13.
Can anyone can explain me the logic or data structure , algo behind it to solve it ?
Thanks In Advance.
Any help or what so ever is appreciated .
You can binary search for the answer.
To check if an answer is correct: keep adding toffees to the 1st box as long it's total is less than answer. Once done, move on to the next box. If you can accommodate all toffees, your answer would work, and you can binary search for the lower half. If you cannot, move on to the higher half.
Edge case would be M > N. If M <=N, then your answer would work even if you have some boxes left, as you can simply transfer some toffees from one of the used box to the empty box. Capacity of both would still be < answer.
Problem link?
Binary search on maximum number of toffees
Thanks.