制作 m 束花所需的最少天数

题目如下:

给你一个整数数组 bloomDay,以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时,需要使用花园中 相邻的 k 朵花 。

花园中有 n 朵花,第 i 朵花会在 bloomDay[i] 时盛开,恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

做题思路:

首先如果总的花数量小于所需要的花数量直接返回-1;否则无论如何都会有满足的天数。

对于辅助函数的实现,可以遍历数组 ,计算其中的长度为k, 且最大元素不超过设定的值,不重合的连续子数组的数量,如果符合要求的不重合的连续子数组的数量大于或等于 m 则返回 true,否则返回 false。

我们可以使用二分查找,这样就可以避免设定的值太小或者太大,太小的话辅助函数一直返回false,效率很低,太大的话无论如何都是true,导致返回的天数会非常大。

这是实现功能的主要函数,其中复用了辅助函数进行判断

int minDays(vector<int>& bloomDay, int m, int k) {
        if(m > bloomDay.size() / k)
        {
            return -1;
        }
        int low=INT_MAX,high=0;
        int num=bloomDay.size();
        for(int i=0;i<num;i++)
        {
            low=min(bloomDay[i],low);
            high=max(bloomDay[i],high);
        }
        while(low<high)
        {
            int days=(high-low)/2+low;
            if(truee(bloomDay,days,m,k))
            {
                high=days;
            }
            else
            {
                low=days+1;
            }
        }
        return low;
    }

辅助函数中主要是对数组中连续的花朵天数进行判断,如果符合要求则返回true。

bool truee(vector<int>& bloomDay,int days,int m,int k)
    {
        int num=0;
        int sum=0;
        int sizes=bloomDay.size();
        for(int i=0;i<sizes&&num<m;i++)
        {
            if(bloomDay[i]<=days)
            {
                sum++;
                if(sum==k)
                {
                    num++;
                    sum=0;
                }
            }
            else{
                sum=0;
            }
        }
        return num>=m;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/572465.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SpringMVC基础篇(一)

文章目录 1.基本介绍1.特点2.SpringMVC跟SpringBoot的关系 2.快速入门1.需求分析2.图解3.环境搭建1.创建普通java工程2.添加web框架支持3.配置lib文件夹1.导入jar包2.Add as Library3.以后自动添加 4.配置tomcat1.配置上下文路径2.配置热加载 5.src下创建Spring配置文件applica…

React.js 3D开发快速入门

如果你对 3D 图形的可能性着迷&#xff0c;但发现从头开始创建 3D 模型的想法是不可能的 - 不用担心&#xff01; Three.js 是一个强大的 JavaScript 库&#xff0c;它可以帮助我们轻松地将现有的 3D 模型集成到 React 应用程序中。因此&#xff0c;在本文中&#xff0c;我将深…

Educational Codeforces Round 164 (Rated for Div. 2) A-E

A. Painting the Ribbon 暴力模拟即可 #include <bits/stdc.h>using namespace std; const int N 2e5 5; typedef long long ll; typedef pair<ll, ll> pll; typedef array<ll, 3> p3; // int mod 998244353; const int maxv 4e6 5; // #define endl &…

ICCV2023人脸识别TransFace论文及代码学习笔记

论文链接&#xff1a;https://arxiv.org/pdf/2308.10133.pdf 代码链接&#xff1a;GitHub - DanJun6737/TransFace: Code of TransFace 背景 尽管ViTs在多种视觉任务中展示了强大的表示能力&#xff0c;但作者发现&#xff0c;当应用于具有极大数据集的人脸识别场景时&#…

Leaflet实现离线地图展示,同时显示地图上的坐标点和热力图

在实际工作中,因为部署环境的要求,必须使用离线地图,而不是调用地图接口。我们应该怎么解决这种项目呢? 下面介绍一种解决该问题的方案:Leaflet+瓦片地图 一、Leaflet Leaflet 是一个开源并且对移动端友好的交互式地图 JavaScript 库。 它大小仅仅只有 42 KB of JS, 并且拥…

opencv图片绘制图形-------c++

绘制图形 #include <opencv2/opencv.hpp> #include <opencv2/core.hpp> #include <filesystem>bool opencvTool::drawPolygon(std::string image_p, std::vector<cv::Point> points) {cv::Mat ima cv::imread(image_p.c_str()); // 读取图像&#xf…

如何调节电脑屏幕亮度?让你的眼睛更舒适!

电脑屏幕亮度的调节对于我们的视力保护和使用舒适度至关重要。不同的环境和使用习惯可能需要不同的亮度设置。可是如何调节电脑屏幕亮度呢&#xff1f;本文将介绍三种不同的电脑屏幕亮度调节方法&#xff0c;帮助您轻松调节电脑屏幕亮度&#xff0c;以满足您的需求。 方法1&…

C++必修:从C到C++的过渡(下)

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C学习 贝蒂的主页&#xff1a;Betty’s blog 1. 缺省参数 1.1. 缺省参数的使用 缺省参数是声明或定义函数时为函数的参数指定…

直接插入排序与希尔排序的详解及对比

目录 1.直接插入排序&#xff08;至少有两个元素才可以使用&#xff09; 排序逻辑 B站动画演示&#xff1a;直接插入排序 逻辑转为代码&#xff1a; 稳定性&#xff1a;稳定 时间复杂度&#xff1a;O(N^2) 空间复杂度&#xff1a;O(1) 应用场景 2.希尔排序&#xff08;对…

VUE父组件向子组件传递值

创作灵感 最近在写一个项目时&#xff0c;遇到了这样的一个需求。我封装了一个组件&#xff0c;这个组件需要被以下两个地方使用&#xff0c;一个是搜索用户时用到&#xff0c;一个是修改用户信息时需要用到。其中&#xff0c;在搜索用户时&#xff0c;可以根据姓名或者账号进…

C++之STL-String

目录 一、STL简介 1.1 什么是STL 1.2 STL的版本 1.3 STL的六大组件 ​编辑 1.4 STL的重要性 二、String类 2.1 Sting类的简介 2.2 string之构造函数 2.3 string类对象的容量操作 2.3.1 size() 2.3.2 length() 2.3.3 capacity() 2.3.4 empty() 2.3.5 clear() 2.3.6…

【Unity】苹果(IOS)开发证书保姆级申请教程

前言 我们在使用xcode出包的时候&#xff0c;需要用到iOS证书(.p12)和描述文件(.mobileprovision) 开发证书及对应的描述文件用于开发阶段使用&#xff0c;可以直接将 App 安装到手机上&#xff0c;一个描述文件最多绑定100台测试设备 1.证书管理 进入网站Apple Developer &…

从虚拟化走向云原生,红帽OpenShift“一手托两家”

汽车行业已经迈入“软件定义汽车”的新时代。吉利汽车很清醒地意识到&#xff0c;只有通过云原生技术和数字化转型&#xff0c;才能巩固其作为中国领先汽车制造商的地位。 和很多传统企业一样&#xff0c;吉利汽车在走向云原生的过程中也经历了稳态业务与敏态业务并存带来的前所…

视频美颜SDK原理与实践:从算法到应用

当下&#xff0c;从社交媒体到视频通话&#xff0c;人们越来越依赖于视频美颜功能来提升自己的形象。而视频美颜SDK作为支撑这一技术的重要工具&#xff0c;其原理和实践至关重要。 一、什么是视频美颜SDK&#xff1f; 视频美颜SDK是一种软件开发工具包&#xff0c;用于集成到…

FloodFill算法---DFS

目录 floodfill算法概念&#xff1a; 算法模板套路&#xff1a; 例题1&#xff1a;图像渲染 例题2&#xff1a;岛屿数量 例题3&#xff1a;岛屿的最大面积 例题4&#xff1a;被围绕的区域 floodfill算法概念&#xff1a; floodfill算法是一种常用的图像处理算法&#xf…

【IDEA】在IntelliJ IDEA中导入Eclipse项目:详细指南

IntelliJ IDEA和Eclipse是两款常用的集成开发环境&#xff08;IDE&#xff09;&#xff0c;在软件开发中经常会遇到需要在它们之间迁移项目的情况。本文将重点介绍如何在IntelliJ IDEA中导入Eclipse项目&#xff0c;以帮助开发者顺利地迁移他们的项目&#xff0c;并在IntelliJ …

云主机修复监控插件异常的方法

首先&#xff0c;进入云监控服务--选择主机监控&#xff0c;勾选上网络配置异常的云主机&#xff0c;最上面的修复插件配置&#xff0c;然后等待大约半个小时多&#xff0c;再观察下主机的状态。 一般情况下问题都可以被解决&#xff0c;如果解决不了&#xff0c;可以尝试卸载…

剑指 Offer 03.:数组中重复的数字

剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0&#xff5e;n-1 的范围内。数组中某些数字是重复的&#xff0c;但不知道有几个数字重复了&#xff0c;也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。…

Linux下的进程管理:创建、终止、切换与等待

文章目录 一、引言二、进程创建1、进程创建的概念与场景2、进程创建的方式a、fork() 系统调用b、fork() 后的执行流程 3、进程创建的过程a、进程创建过程b、子进程创建过程 4、父子进程关系与属性继承 三、进程终止1、进程终止的原因2、进程的错误码和退出码a、错误码b、退出码…
最新文章