Leetcode1760:袋子里最少数目的球

ops/2025/2/13 7:09:48/

题目描述:

给你一个整数数组 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.ppmy.cn/ops/157986.html

相关文章

【力扣】146.LRU缓存

AC截图 题目 思路 可以构造一个双向链表&#xff0c;使用dummy作为哨向结点。 ①定义结点 class Node{ public:int key;int value;Node* prev;Node* next;Node(int k0,int v0):key(k),value(v){} }; LRUCache类 ②定义参数列表 int capacity;Node* dummy;unordered_map<i…

npm与包

在 Node.js 的生态系统中&#xff0c;npm&#xff08;Node Package Manager&#xff09;扮演着至关重要的角色。它不仅是管理项目依赖的强大工具&#xff0c;还提供了丰富的第三方库和工具&#xff0c;极大地提高了开发效率。本文将详细介绍 npm 的基本概念、常用命令以及如何创…

9.4双向BFS

一、双向BFS核心思想 双向广度优先搜索&#xff08;Bidirectional BFS&#xff09;是一种优化策略&#xff0c;通过从起点和终点同时进行BFS&#xff0c;在中间相遇时终止搜索。适用于&#xff1a; 明确起点和终点的场景搜索空间较大的最短路径问题分支因子&#xff08;Branc…

开源机器人+具身智能 解决方案+AI

开源机器人、具身智能(Embodied Intelligence)以及AI技术的结合,可以为机器人领域带来全新的解决方案。以下是这一结合的可能方向和具体方案: 1. 开源机器人平台 开源机器人平台为开发者提供了灵活的基础架构,可以在此基础上结合具身智能和AI技术。以下是一些常用的开源机…

网络安全之探险

因为工作相关性&#xff0c;看着第三方公司出具的网络安全和shentou测试报告就想更深入研究一下&#xff0c;于是乎开始探索网络安全方面的知识&#xff0c;度娘、知乎开始一步步开始&#xff0c;总结昨天学到皮毛知识。 1.考证大全&#xff0c;开始是奔着这个目的去的 2.有用…

C++ Primer 条件语句

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…

【第三节】CMake 的构建流程

前言 CMake 是一个跨平台的构建工具&#xff0c;广泛用于管理 C 项目的构建过程。它的核心优势在于能够生成适合不同平台的构建文件&#xff08;如 Makefile、Ninja 文件、Visual Studio 工程等&#xff09;&#xff0c;从而简化项目的编译和构建流程。本文将详细介绍 CMake 的…

npm和pnpm的区别

1. 依赖存储机制 npm 默认使用 扁平化结构&#xff08;node_modules&#xff09;&#xff0c;所有依赖直接安装在项目的 node_modules 目录下。 依赖可能存在重复安装&#xff08;尤其是不同版本&#xff09;&#xff0c;导致 磁盘空间浪费。 依赖提升&#xff08;hoisting…