Leetcode1760:袋子里最少数目的球

题目描述:

给你一个整数数组 nums ,其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次:

  • 选择任意一个袋子,并将袋子里的球分到 2 个新的袋子中,每个袋子里都有 正整数 个球。
    • 比方说,一个袋子里有 5 个球,你可以把它们分到两个新袋子里,分别有 1 个和 4 个球,或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ,你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

代码思路:

  1. 初始化边界
    • l(left)初始化为 1,因为最小的开销可以是 1(即每个袋子最多只有一个球)。
    • r(right)初始化为 max(nums),因为不进行任何操作时,开销的最大值就是数组中的最大值。
  2. 二分查找
    • 使用二分查找在 [l, r] 范围内寻找满足条件的最小开销。
    • 每次计算中间值 mid 作为当前的候选开销。
  3. 计算操作数
    • 对于数组中的每个袋子 x,计算将其球数分到不超过 mid 的开销所需的操作数。
    • 由于每次操作是将一个袋子分成两个袋子,并且每个袋子里的球数都是正整数,所以我们需要将 x 个球分到不超过 mid 的两个袋子中。
    • 最坏情况下,我们需要将 x 个球分到 mid 和 x-mid(或 ceil(x/2) 和 floor(x/2),取决于 x 是奇数还是偶数)两个袋子中,但因为我们只关心操作次数,所以只需要考虑将 x 个球分到尽可能接近 mid 的两个袋子中。
    • 由于每次操作至少会减少一个袋子(因为我们把一个袋子分成了两个),所以我们可以将 x 个球分到不超过 mid 的袋子中的操作次数近似为 (x-1)//mid(向下取整,因为每次操作减少一个球,直到剩余球数不超过 mid)。
    • 注意这里的 (x-1)//mid 实际上是在计算将 x 个球分到不超过 mid 的袋子中,最多需要进行多少次“拆分”操作(每次操作至少减少一个袋子,但球的总数减少 mid 或更少时,需要多次操作才能达到每个袋子不超过 mid)。
  4. 调整边界
    • 如果计算出的总操作数 op 大于 maxOperations,说明当前的 mid 作为开销太小,无法在给定的操作次数内完成,因此需要增大开销,将 l 更新为 mid+1
    • 否则,当前的 mid 可能是一个可行的解(但不一定是最小的),因此尝试减小开销,将 r 更新为 mid(因为 mid 也可能是一个解,所以这里用 mid 而不是 mid-1 来更新 r,以确保不会错过 mid 这个可能的解)。
  5. 返回结果
    • 当 l 和 r 相等时,循环结束,此时 l(或 r)即为满足条件的最小开销。 

代码实现:

class Solution:def minimumSize(self, nums: list[int], maxOperations: int) -> int:l,r=1,max(nums)while l<r:mid=(l+r)>>1if (op:=sum([ (x-1)//mid for x in nums]))>maxOperations:l=mid+1else:r=midreturn l

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Gui-Guider1.8.1 数字时钟控件找不到定义,无法编译

我们在Gui-Guider中使用的一些控件&#xff0c;生成后会发现在LVGL源码中找不到该控件的定义&#xff0c;这时因为Gui-Guider中的一些控件是其自己编写的而不是LVGL提供的&#xff0c;那么我们该如何应用呢&#xff1f;这里拿Digital Clock数字时钟控件举例&#xff1a; 这里我…

使用 SDKMAN! 在 Mac(包括 ARM 架构的 M1/M2 芯片)安装适配 Java 8 的 Maven

好的&#xff0c;这是使用 SDKMAN! 安装适配 Java 8 的 Maven 的步骤&#xff1a; 前提条件: 安装 SDKMAN!: 如果你的系统上没有安装 SDKMAN!&#xff0c;请按照以下说明进行安装: curl -s "https://get.sdkman.io" | bash source "$HOME/.sdkman/bin/sdkman-i…

【Stable Diffusion模型测试】测试ControlNet,没有线稿图?

相信很多小伙伴跟我一样&#xff0c;在测试Stable Diffusion的Lora模型时&#xff0c;ControlNet没有可输入的线稿图&#xff0c;大家的第一反应就是百度搜&#xff0c;但是能从互联网上搜到的高质量线稿图&#xff0c;要么收费&#xff0c;要么质量很差。 现在都什么年代了&a…

oracle表分区--范围分区

文章目录 oracle表分区分区的原因分区的优势oracle表分区的作用oracle表分区类型一、范围分区二、 创建分区表和使用&#xff1a;1、按照数值范围划分2、按照时间范围3、MAXVALUE2. 向现有表添加新的分区3、 分区维护和重新组织&#xff08;合并/删除&#xff09; oracle表分区…

InspurServer服务器监控指标详解

在现代信息化环境中&#xff0c;服务器的稳定运行对于业务连续性至关重要。InspurServer作为高性能服务器解决方案&#xff0c;其性能监控与优化更是不可或缺。本文将基于监控易一体化运维软件&#xff0c;深入探讨InspurServer服务器的关键监控指标&#xff0c;包括响应时间、…

基于opencv的 24色卡IQA评测算法源码-可完全替代Imatest

1.概要 利用24色卡可以很快的分析到曝光误差&#xff0c;白平衡误差&#xff0c;噪声&#xff0c;色差&#xff0c;饱和度&#xff0c;gamma值。IQA或tuning工程一般用Imatest来手动计算&#xff0c;不便于产测部署&#xff0c;现利用opencv实现了imatest的全部功能&#xff0c…

Django开发入门 – 4.创建Django app

Django开发入门 – 4.创建Django app Create A Django App Under An Existing Project By JacksonML 1. 什么是Django app? Django项目面向Web应用程序&#xff0c;它会由一个或多个子模块组成&#xff0c;这些子模块称为apps。 Django apps负责执行完整Web应用程序中涉及…

string

string 概念 string 字符串其实是一种更加高级的封装,string字符串中包含大量的方法, 这些方法使得字符串的操作变得更加简单。 C中将字符串直接作为一种类型,也就是string类型,使用string类型创建的 对象就是C的字符串。 使用C中提供的string是,必须添加头文件string。 st…

如何在Excel和WPS中进行翻译

文档翻译我们可以用在线翻译工具&#xff0c;Excel工作表的翻译使用在线翻译工具就不是特别方便&#xff0c;那么如何快速进行翻译呢&#xff0c;我们今天介绍在不同的场景下如何利用翻译函数和Python程序来实现单元格的快速翻译。 一、在wps中进行翻译 WPS是我们常用的办公软…

Docker Desktop Windows 之 安装 SqlServer

Docker 安装SqlServer 》》拉取 Pull docker pull mcr.microsoft.com/mssql/server:2022-latest 》》运行 run docker run -e “ACCEPT_EULAY” -e “MSSQL_SA_PASSWORDSA12345” -p 1400:1433 --name sql-server2022 -h sql-server2022 -d mcr.microsoft.com/mssql/server:20…

【STM32】ADC|多通道ADC采集

本次实现的是ADC实现数字信号与模拟信号的转化&#xff0c;数字信号时不连续的&#xff0c;模拟信号是连续的。 1.ADC转化的原理 模拟-数字转换技术使用的是逐次逼近法&#xff0c;使用二分比较的方法来确定电压值 当单片机对应的参考电压为3.3v时&#xff0c;0~ 3.3v(模拟信…

pdf.js默认显示侧边栏和默认手形工具

文章目录 默认显示侧边栏(切换侧栏)默认手形工具(手型工具) 大部分的都是在viewer.mjs中的const defaultOptions 变量设置默认值,可以使用数字也可以使用他们对应的变量枚举值 默认显示侧边栏(切换侧栏) 在viewer.mjs中找到defaultOptions,大概在732行,或则搜索sidebarViewOn…

使用DeepSeek和Kimi快速自动生成PPT

目录 步骤1&#xff1a;在DeepSeek中生成要制作的PPT主要大纲内容。 &#xff08;1&#xff09;在DeepSeek网页端生成 &#xff08;2&#xff09;在本地部署DeepSeek后&#xff0c;使用chatBox生成PPT内容 步骤2&#xff1a;将DeepSeek成的PPT内容复制到Kimi中 步骤3&…

PADS多层板减少层数

前提 PADS是硬件工程师必备的画图软件&#xff0c;相信很多朋友遇到过为降低成本把6层板改为4层&#xff0c;或8层改为6层的经历&#xff0c;正常是把不需要的两层上所有东西删掉&#xff0c;然后修改层设置&#xff0c;下面举例说明。 首先是将要删除的层上的数据全部删除&a…

Spring 项目接入 DeepSeek,分享两种超简单的方式!

⭐自荐一个非常不错的开源 Java 面试指南&#xff1a;JavaGuide &#xff08;Github 收获148k Star&#xff09;。这是我在大三开始准备秋招面试的时候创建的&#xff0c;目前已经持续维护 6 年多了&#xff0c;累计提交了 5600 commit &#xff0c;共有 550 多位贡献者共同参与…

【LeetCode】689、三个无重叠子数组的最大和

【LeetCode】689、三个无重叠子数组的最大和 文章目录 一、dp1.1 dp 二、多语言解法 一、dp 1.1 dp // go // 输入: nums[] // 计算: 找三段长度为 k 的不重叠的子数组. 要求这 3k 个元素之和最大 // 输出: 三段子数组的 起始位置. 若有多个结果, 返回字典序最小的一个 func …

transformer

导语&#xff1a; 2017年&#xff0c;一篇名为《Attention is All You Need》的论文横空出世&#xff0c;提出了Transformer模型&#xff0c;彻底改变了自然语言处理&#xff08;NLP&#xff09;领域的格局。Transformer以其独特的结构和强大的性能&#xff0c;迅速成为NLP领域…

DeepScaleR:仅用 1.5B 参数超越 OpenAI O1-Preview 的强化学习模型

1. 项目概述 1.1 项目目标与意义 DeepScaleR 项目旨在通过强化学习技术推动人工智能模型的性能提升,以更低的成本实现更优的推理能力。其核心目标是开发出在特定任务上超越现有模型的高效模型,同时为开源社区提供技术参考,促进技术的普惠和创新。 技术突破:DeepScaleR-1.…

深入理解指针初阶:从概念到实践

一、引言 在 C 语言的学习旅程中&#xff0c;指针无疑是一座必须翻越的高峰。它强大而灵活&#xff0c;掌握指针&#xff0c;能让我们更高效地操作内存&#xff0c;编写出更优化的代码。但指针也常常让初学者望而生畏&#xff0c;觉得它复杂难懂。别担心&#xff0c;本文将用通…

八、OSG学习笔记-

前一章节&#xff1a; 七、OSG学习笔记-碰撞检测-CSDN博客https://blog.csdn.net/weixin_36323170/article/details/145558132?spm1001.2014.3001.5501 一、了解OSG图元加载显示流程 本章节代码&#xff1a; OsgStudy/wids CuiQingCheng/OsgStudy - 码云 - 开源中国https:…