1507. Round Cake Slices
A round cake is already cut into n slices arranged in a circle, and slices[i] is the weight of slice i; slice n - 1 is next to slice 0. The baker wants to hand out the whole cake to k guests. Each guest gets one non-empty block of consecutive slices (an arc of the circle), the blocks do not overlap and together they cover every slice.
Return the largest possible weight of the lightest block, as a long. You may choose where the circle is opened. Hint: binary search the target weight X. On the doubled array, compute for each position the first index where the running weight reaches X using two pointers, then use binary lifting to see whether some start finishes k blocks within one lap. Aim for O(n log n log S) time, where S is the total weight, and O(n log k) or better space.
Example 1
- Input:
- slices = [4,1,3,7,2], k = 2
- Output:
- 8
- Explanation:
Blocks 7+2 = 9 and 4+1+3 = 8 are the best split, so the lightest block weighs 8.
Example 2
- Input:
- slices = [5,5,5,5], k = 4
- Output:
- 5
- Explanation:
With as many guests as slices every block is a single slice, so the lightest is 5.
Example 3
- Input:
- slices = [9,2], k = 1
- Output:
- 11
- Explanation:
One guest takes the whole cake, a block of weight 11.
Constraints
1 ≤ k ≤ n ≤ 2000
1 ≤ slices[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log k log S)
- Space
- O(n)