Minimum Eating Speed

Difficulty: 1600 3500 ms 128 MB

binary-search

There are N banana piles; eating at speed k clears ⌈p/k⌉ hours per pile (one pile per hour session). Find the minimum integer speed to finish all piles within H hours.

Input: the first line has N and H (H ≥ N); the second line has the N pile sizes.

Output: the minimum speed k.

Constraints:

• 1 ≤ N ≤ 10⁵
• N ≤ H ≤ 4×10⁵
• 1 ≤ p_i ≤ 10⁹

Sample Tests

4 8
3 6 7 11

4

1 1
1000000000

1000000000

Read the Editorial