Koko Eating Bananas
Annual Banana Festival is here in Umbristan. The Annual Banana Festival is one of the most renowned cultural celebration in Umbristan, and Koko is very excited because she loves eating bananas and banana foods. Banana smoothie, banana boat, you name it, she loves it.
Out of the n at the fair stands selling bananas, each stand sells a
unique banana dish, Koko wants to try all of them. In fact, for the ith stand, Koko wants to
have at least min_cals[i] Calories of food (Did you know that Calories and calories
are different? 1 Cal = 1 kcal = 1000 cal). During each hour while the fair is open to the
public, she can eat from one stand as much food as she wants.
Problem is, the fair is open to the public for a limited time - h hours to be exact -
yet she would like to eat as much as she wants before the fair ends.
However, as she is on a diet, she would like to reduce the max Calories of food she eats in an hour. You
understand her struggle, so you would like to help.
Find the least maximum Calories she can eat per hour that allows her to eat what she wants before the fair closes for the public.
Input
min_cals: A list of Calories Koko wants to each from the food of each stand.h: The number of hours the fair opens for.
Output
The least maximum Calories she can eat.
Examples
Example 1:
Input:
min_cals = [3, 6, 7, 11] h = 8
Output: 4
Explanation:
For the eight hours that are open, Koko can do this:
- For the
1st hour, eat3Cal from the first stand. - For the
2nd and the3rd hour, eat3Cal each from the second stand. - For the
4th hour, eat3Cal from the third stand, and for the5th hour, eat4Cal from it. - For the
6th hour, eat3Cal from the fourth stand, and for the next2hours, eat4Cal each.
Koko can finish eating everything she wants within 8 hours, with the max Calories per hour being 4.
Any smaller value will cause her to spend more time to eat, exceeding the time limit.
Constraints
1 <= len(min_cals) <= 10^4len(min_cals) <= h <= 10^91 <= min_cals[i] <= 10^9