首页 > 其他分享 >力扣875. 爱吃香蕉的珂珂(二分查找)

力扣875. 爱吃香蕉的珂珂(二分查找)

时间:2023-06-22 16:33:08浏览次数:43  
标签:二分 香蕉 piles int minEatingSpeed 875 mid 力扣 小时

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

换句话说,就是找到吃的最慢且能吃完的速度,其实仔细理解一下发现就是 ————— 查找某个函数f(k)中 k 的 最小值 , 所以我们用最快的二分就好了。

​
class Solution {
    public  int minEatingSpeed(int[] piles, int h) {
        int l = 1;
        int r = Arrays.stream(piles).max().getAsInt();
        int minEatingSpeed = minEatingSpeed(piles, h, l, r);
        return minEatingSpeed;
    }
    public  int minEatingSpeed(int[] piles, int h, int l, int r) {
        //二分查找
        while (l < r) {
            int mid = l + (r - l) / 2;
​
            //以mid作为速度,获取吃的时间,如果发现小于等于指定的时间h,说明以当前mid作为速度可能还是吃的太快了。
            if (eatingTime(piles, mid) <= h) {
                r = mid;
            } else {
                l = mid + 1;    //如果大于指定时间h,说明吃的速度慢了,去数组右边找。
            }
        }
        return l;
    }
​
    public  int eatingTime(int[] piles, int k) {                 
        int eatTime = 0;
        for (int pile : piles) {                                //这里就是所谓的函数f(k)
            eatTime += pile / k + (pile % k > 0 ? 1 : 0);          //用堆除以吃的速度,如果有余,就再+1小时,这样就算出来一堆要吃几个小时
        }
        return eatTime;
    }
​
}

 

标签:二分,香蕉,piles,int,minEatingSpeed,875,mid,力扣,小时
From: https://www.cnblogs.com/hanlinyuan/p/17497973.html

相关文章

  • 二分查找法lowerCeil版(找某个重复值的最小下标)利用二分upper法实现
    也是利用二分的upper法实现的,不知道什么是upper?看这里->二分查找法upper版(找大于某个值的最小下标)递归+非递归版-翰林猿-博客园(cnblogs.com)思路:先利用upper找到上界的index拿着index-1的下标(也就是重复值的最大下标)向前遍历,一直到遍历到发现不相等的元素即可。......
  • 二分查找法ceil版(找某个重复值的最大下标)利用二分upper法实现
    如果有等于target的元素就返回最大的下标元素。如果没有等于target的元素,那么就返回大于target的最小元素,即这一篇文章实现的upper函数。二分查找法upper版(找大于某个值的最小下标)递归+非递归版-翰林猿-博客园(cnblogs.com),当然你们也可以更改返回值-1什么的作为查找......
  • 二分查找法upper版(找大于某个值的最小下标)递归+非递归版
    需求:比如说查询一个班级大于60分的最低分等等。思路与二分法基本相同,只不过是对比的逻辑发生了一些小变化,这里所说的上界就是指大于某个值的最小下标。当mid<target:说明target的上界还在mid的右边,所以要去找比mid大的当mid>target:说明mid有可能是target的上界,所以......
  • 基础算法:二分,贪心等 学习笔记
    普及组基础算法这些都是零零散散接触过的基础算法,写个笔记把这些整理到一起来。线性降维技巧之前在学校洛谷团队里看到一个题单,觉得这些技巧可能有用,就转存了。前缀和差分前缀和是一种对区间求和问题进行降维的方法。具体地,对于给定数组\(A[n]\),求出\(A[l,r]\)区间和这个......
  • 每日一题力扣 1262 https://leetcode.cn/problems/greatest-sum-divisible-by-three/
    、 题解这道题目核心就算是要知道如果x%3=2的话,应该要去拿%3=1的数字,这样子才能满足%3=0贪心sum不够%3的时候,就减去余数为1的或者余数为2的需要注意两个余数为1会变成余数为2的,所以可能减去2个余数为1核心代码如下publicintmaxSumDivThreeOther(int[]nums){​  ......
  • transform (牛客多校) (双指针+二分+ 中位数妙用+前缀和相减维护)
    题目大意:n个商店在一条直线上, 有一个xi然后有ai个商品你可以把商店的物品移动到另一个商店,代价为:abs(xi-xj)在代价不超过T的情况下你可以选择一个商店来让其他商店的物品都移到这个商店,问最多移动多少个物品  思路:双指针维护一个最大的区间,因......
  • Luogu3168 [CQOI2015] 任务查询系统 - 主席树 - 二分 -
    题目链接:https://www.luogu.com.cn/problem/P3168题解:主席树可以解决一类j静态区间第\(k\)小的问题,我们先来看看这是怎么工作的主席树的本质就是有很多棵线段树,然后发现这些线段树绝大多数都是重叠的,因此可以优化到空间复杂度\(O(n\logn)\)在这里,我们将序列的每一个位置......
  • Primes on Interval(欧拉筛+二分+滑动窗口)
    【题面】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能被其他任何的数字除尽.现在给定一个正整数序列 ,+1,⋯ ,a,a+1,⋯,b (≤)(a≤b),请找出一个最小值 l,使其满足对于任意一个长度为 l 的子串,都包含 k 个质数.......
  • 简单总结最近力扣所写的题
    下面的题目是最近我在力扣上面刷了每日一题之后所做的总结。题目一比较字符串最小字母出现频次定义一个函数 f(s),统计 s  中(按字典序比较)最小字母的出现频次 ,其中 s 是一个非空字符串。例如,若 s="dcce",那么 f(s)=2,因为字典序最小字母是 "c",它出现了 2次。现在,给你......
  • Best Cow Fences(前缀和+特殊二分)
    之前的二分大多数都是整数类型的,今天又学到一种新型的二分,浮点数的二分,浮点数的二分可太巧妙了.且听我细细分说::OpenJudge-2018:BestCowFences#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intn,k;doublea[N],s[N],l,r;boolcheck(doubleu)......