珂珂吃香蕉(js二分查找法)

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

输入:

参数1:piles: number[] 数组里面的值代表每一堆香蕉的根数;
参数2: H: number 输入警卫离开的时间;

输出:

输出最小速度K;

示例 1:

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2:

输入: piles = [3,6,7,13], H = 8
输出: 5

示例 3:

输入: piles = [23,30,12, 4], H = 5
输出: 23

示例 4:

输入: piles = [23,30,12, 4], H = 6
输出: 15

/**
   * @param piles{Array} 香蕉堆
   * @param H{number} 警卫离开的时间H
   * */
  function minEatingSpeed(piles, H) {
    if(H < piles.length) {
      return '离开时间不能小于香蕉堆数';
    }
    if (piles.length === 1) {//特殊情况,只有一个堆,可直接获取时间
      return Math.ceil(piles[0] / H);
    }
    //按照香蕉数从小到大排序
    const sortPiles = piles.sort(function (a, b) {
      return a - b;
    });
    //初始化三个速度,最小速度,最大速度,中间速度
    let left = 1, right = sortPiles[sortPiles.length - 1], mid;
    while (left < right) {
      mid = Math.floor((left + right) / 2);//折中向下取整
      let needHours = 0;//计算以mid速度吃香蕉需要的总时间
      for (let pile of sortPiles) {
        //吃完一堆后,这一小时内不会再吃更多的香蕉,向上取整
        needHours += Math.ceil(pile / mid);
      }
      if (needHours > H) {
        //超过H,则说明我们吃慢了,增大左边界
        left = mid + 1;
      } else {
        //否则缩小右边界
        right = mid;
      }
    }
    return left;
  }
  const K = minEatingSpeed([3,6,7,11], 8);
  console.log("最小速度>>>>>>> ", K);

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 回顾二分搜索树的定义 二分搜索树的重要性质 二分搜索树的重要性质如下,初学的时候经常会被忽略或者错误地理解: 左子...
    李威威阅读 563评论 0 0
  • iOS 苹果官方Demo合集 字数10517阅读21059评论18喜欢144 其实, 开发了这么久, 不得不说, ...
    bingo居然被占了阅读 10,299评论 2 31
  • 荷兰房市目前正处于日新月异的变化之中。购房贷款利息超低,房价上涨,交易活跃。有大量人士加入买房的大军。在这个日益升...
    荣若言阅读 2,039评论 0 0
  • 在开发maven项目时,常常想了解maven的插件做了哪些工作,这时候就需要用到调试maven插件源码 准备工作 ...
    碳头tantou阅读 2,500评论 0 50
  • 2018年元月12日下午上海五金商业行业协会年会在好美家装潢建材有限公司热烈举行.中国五交化商业行业协会秘书长、北...
    无友不如己阅读 299评论 0 0