首页 > 其他分享 >从实际场景中抽象出二分搜索

从实际场景中抽象出二分搜索

时间:2023-10-04 17:11:07浏览次数:40  
标签:二分 香蕉 场景 题目 target piles int hours 抽象

参考:1011. 在 D 天内送达包裹的能力;875. 爱吃香蕉的珂珂

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

看完题目之后可能很难联想到解决问题需要用到二分搜索,但是我们可以这样想,实际应用中,我们很难碰到一种情况,即把可能的答案列出来,还排好序,我们在这里面找到满足需求的target答案,一般来说,我们可能有一个target这是我们需要达到的目标,此外可能如同函数一样可能的答案与结果target存在一种映射关系,f(x),x代表了我们的搜索空间,不同的x映射了不同的结果,而我们的目标就是找到满足target的x,严格来说满足target的x可能有无数个,但是题目一般会限定最大OR最小,而f(x)一般就是题目所给的规则,这个f(x)一般需要自己去抽象出来。比如本题:

    // 定义:速度为 x 时,需要 f(x) 小时吃完所有香蕉
    // f(x) 随着 x 的增加单调递减
    int f(vector<int>& piles, int x) {
        int hours = 0;
        for (int i = 0; i < piles.size(); i++) {
            hours += piles[i] / x;
            if (piles[i] % x > 0) {
                hours++;
            }
        }
        return hours;
    }

对于f(x)的抽象应该是这种题目的一个难点,需要仔细阅读题目,这一点我还要继续训练

标签:二分,香蕉,场景,题目,target,piles,int,hours,抽象
From: https://www.cnblogs.com/H-force/p/17742479.html

相关文章

  • Golang struct 结构体 面向对象编程思想-抽象 理解抽象
    我们在前面去定义一个结构体时候,实际上就是把一类事物的共有的属性(字段)和行为(方法)提取出来,形成一个物理模型(模板),这种研究问题的方法称为抽象。当你将一类事物的属性和行为抽取出来之后,下一步就是将代码体现出来。下面就是模拟银行卡存款取款查询余额方式。packagemainimport"fm......
  • 前端 | 说说 HTTP 常见的状态码有哪些,适用场景
    前端|说说HTTP常见的状态码有哪些,适用场景?基本描述HTTP状态码(英语:HTTPStatusCode),用以表示网页服务器超文本传输协议响应状态的3位数字代码它由RFC2616规范定义的,并得到RFC2518、RFC2817、RFC2295、RFC2774与RFC4918等规范扩展简单来讲,http状态码的作用是服务器......
  • 迷失岛2笔记3 场景数据保存
     首先我们注册一下这个场景前后数据变化的事件 然后在我们切换场景这里做一个场景前场景后的一个数据切换 事件调用 然后再里面写逻辑   可以看到上面的字典他是一个枚举和一个Bool 就是用这个来判断哪些物品是否要激活使用过   他就是查找当前场......
  • pyqt5-QAbstractButton抽象按钮类
    1、介绍QAbstractButton,抽象按钮类。该类定义了按钮类型组件的常用方法和事件,是QPushButton按钮组件、QCheckBox多选按钮组件、QRadioButton单选按钮组件的直接父类。另一方面,该类直接继承QWidget类。2、基础使用setText(self,text:str)设置文本text(self)->str获取......
  • 【中秋国庆不断更】OpenHarmony多态样式stateStyles使用场景
    @Styles和@Extend仅仅应用于静态页面的样式复用,stateStyles可以依据组件的内部状态的不同,快速设置不同样式。这就是我们本章要介绍的内容stateStyles(又称为:多态样式)。概述stateStyles是属性方法,可以根据UI内部状态来设置样式,类似于css伪类,但语法不同。ArkUI提供以下四种状态:​......
  • 【中秋国庆不断更】OpenHarmony多态样式stateStyles使用场景
    @Styles和@Extend仅仅应用于静态页面的样式复用,stateStyles可以依据组件的内部状态的不同,快速设置不同样式。这就是我们本章要介绍的内容stateStyles(又称为:多态样式)。概述stateStyles是属性方法,可以根据UI内部状态来设置样式,类似于css伪类,但语法不同。ArkUI提供以下四种状态:......
  • 【中秋国庆不断更】OpenHarmony多态样式stateStyles使用场景
    @Styles和@Extend仅仅应用于静态页面的样式复用,stateStyles可以依据组件的内部状态的不同,快速设置不同样式。这就是我们本章要介绍的内容stateStyles(又称为:多态样式)。概述stateStyles是属性方法,可以根据UI内部状态来设置样式,类似于css伪类,但语法不同。ArkUI提供以下四种状态:​......
  • C++ STL标准容器的特点和典型的使用场景
    概念和作用C++标准模板库(StandardTemplateLibrary,STL)提供了一组通用的模板类和函数,用于处理常见的数据结构和算法。STL中的标准容器是其中的重要组成部分,它们提供了不同的数据结构和操作方式,适用于各种不同的使用场景。说白了,就是每一种容器代表一种特定的数据结构。我们在学C......
  • 安防视频监控/视频融合平台EasyCVR可完成的多场景应用
    TSINGSEE青犀视频人员/区域入侵功能通过AI算法后台的实时监测和告警系统,对重要区域进行全天候的监控和管控。一旦监测到有人员靠近、闯入等异常情况,即刻发出告警通知管理人员,从被动的监督转变为主动的监控,实现事前预警、事中检测、事后规范处理,极大提升了监控区域的管控效率。 ......
  • 分析视频监控/视频汇聚平台EasyCVR分析网关车辆检测/车牌识别算法及应用场景
    在数字化时代,由于大众对出行要求的提升,汽车数量不断增加,给城市和交通管理带来了很多挑战。为了应对这些问题,旭帆科技开发了一套AI智能车辆检测与车牌识别算法,为交通管理和车辆安全提供高效的解决方案。AI车辆检测和车牌识别算法集成了多种技术,如光学字符识别(OCR)和云计算等,能够从......