#P0051. 爱吃香蕉的珂珂

爱吃香蕉的珂珂

题目描述

珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开,将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 k 根。如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数)。

输入格式

  • 第一行包含两个整数 n 和 h(1≤n≤1041 \leq n \leq 10^4,1≤h≤1091 \leq h \leq 10^9),表示有 n 堆香蕉,珂珂将在 h 小时后见到警卫。
  • 第二行包含 n 个整数 piles[i](1≤piles[i]≤1091 \leq piles[i] \leq 10^9),表示每堆香蕉的数量。

输出格式

  • 输出一个整数,表示珂珂可以在 h 小时内吃掉所有香蕉的最小速度 k。

样例 #1

样例输入 #1

4 8
3 6 7 11

样例输出 #1

4

解释

在这 8 小时内,珂珂选择以速度 4 吃香蕉,可以满足条件:

  • 第一堆:3 根,吃掉 3 根,用时 1 小时。
  • 第二堆:6 根,第一个小时吃掉 4 根,第二个小时吃掉剩下的 2 根,用时 2 小时
  • 第三堆:7 根,吃掉 4 根,用时 1 小时,吃掉剩下的 3 根,用时 1 小时
  • 第四堆:11 根,分三次吃,4 + 4 + 3 根。总共花费 3 小时

总共需要 1 + 2 + 2 + 3 = 8 小时,刚好满足。

样例 #2

样例输入 #2

5 5
30 11 23 4 20

样例输出 #2

30

解释

珂珂最小速度为 30,可以在 5 小时内吃完所有香蕉。因为她每小时最多吃 30 根香蕉,在每堆香蕉上消耗的时间如下:

  • 第一堆:30 根,吃完需要 1 小时。
  • 第二堆:11 根,吃完需要 1 小时。
  • 第三堆:23 根,吃完需要 1 小时。
  • 第四堆:4 根,吃完需要 1 小时。
  • 第五堆:20 根,吃完需要 1 小时。

总共需要 5 小时。

样例 #3

样例输入 #3

5 6
30 11 23 4 20

样例输出 #3

23

解释

珂珂最小速度为 23,能够在 6 小时内吃完所有香蕉。每小时最多吃 23 根香蕉,每堆消耗的时间如下:

  • 第一堆:30 根,吃完需要 2 小时。
  • 第二堆:11 根,吃完需要 1 小时。
  • 第三堆:23 根,吃完需要 1 小时。
  • 第四堆:4 根,吃完需要 1 小时。
  • 第五堆:20 根,吃完需要 1 小时。

总共需要 2 + 1 + 1 + 1 + 1 = 6 小时。

提示

  • 1 <= n <= 10410^4
  • 1 <= h <= 10910^9
  • 1 <= piles[i] <= 10910^9

这个题目的思路是使用二分查找来寻找珂珂能够在给定时间内吃完所有香蕉的最小速度 k。