当前位置: 首页 > news >正文

Leetcode.2171 拿出最少数目的魔法豆

题目链接

Leetcode.2171 拿出最少数目的魔法豆 Rating : 1748

题目描述

给你一个 整数数组 beans,其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中 拿出 一些豆子(也可以 不拿出),使得剩下的 非空 袋子中(即 至少 还有 一颗 魔法豆的袋子)魔法豆的数目 相等一旦魔法豆从袋子中取出,你不能将它放到任何其他的袋子中

请你返回你需要拿出魔法豆的 最少数目

示例 1:

输入:beans = [4,1,6,5]
输出:4
解释:

  • 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。 剩下袋子中魔法豆的数目为:[4,0,6,5]
  • 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为:[4,0,4,5]
  • 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。 剩下袋子中魔法豆的数目为:[4,0,4,4] 总共拿出了 1 + 2 + 1 = 4 个魔法豆,剩下非空袋子中魔法豆的数目相等。 没有比取出 4 个魔法豆更少的方案。

示例 2:

输入:beans = [2,10,3,2]
输出:7
解释:

  • 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为:[0,10,3,2]
  • 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为:[0,10,3,0]
  • 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。 剩下袋子中魔法豆的数目为:[0,10,0,0] 总共拿出了 2 + 2 + 3 = 7 个魔法豆,剩下非空袋子中魔法豆的数目相等。 没有比取出 7 个魔法豆更少的方案。

提示:

  • 1<=beans.length<=1051 <= beans.length <= 10^51<=beans.length<=105
  • 1<=beans[i]<=1051 <= beans[i] <= 10^51<=beans[i]<=105

解法:排序

我们先将豆子 beans按从小到大的顺序排序。

在这里插入图片描述

蓝色的就是要剩下来的豆子,白色的就是要拿走的豆子。

我们用 sum记录所有的豆子。

蓝色部分的豆子:beans[i]∗(n−i)beans[i] * (n - i)beans[i](ni)

白色部分的豆子(要拿走的豆子): sum−beans[i]∗(n−i)sum - beans[i] * (n - i)sumbeans[i](ni)

所以我们只需要从 i=0i = 0i=0遍历到 i=n−1i = n - 1i=n1,遍历一遍,用一个 ans记录最小值即可。

时间复杂度:O(n∗logn)O(n * logn)O(nlogn)

C++代码:

using LL = long long;class Solution {
public:long long minimumRemoval(vector<int>& beans) {LL sum = accumulate(beans.begin(),beans.end(),0LL);sort(beans.begin(),beans.end());int n = beans.size();LL ans = 1e10;for(int i = 0;i < n;i++){ans = min(ans , sum - (n - i) * 1LL * beans[i]);}return ans;}
};

相关文章:

Leetcode.2171 拿出最少数目的魔法豆

题目链接 Leetcode.2171 拿出最少数目的魔法豆 Rating &#xff1a; 1748 题目描述 给你一个 正 整数数组 beans&#xff0c;其中每个整数表示一个袋子里装的魔法豆的数目。 请你从每个袋子中 拿出 一些豆子&#xff08;也可以 不拿出&#xff09;&#xff0c;使得剩下的 非空…...

day1 计算机组成与结构考点汇总

一、重点知识点 计算机硬件组成、运算器、控制器奇偶校验码、循环冗余校验码、海明码指令系统&#xff1a;指令操作数寻址方式、CISC和RISC、指令流水线的计算存储系统&#xff1a;分级存储、局部性原理、cache、主存编址计算、磁盘输入输出技术&#xff1a;程序查询方式、中断…...

Java虚拟机的类加载机制

Java虚拟机的类加载机制综述类的生命周期类加载器双亲委派模型---综述 我们编写的Java代码如何能在一个操作系统上运行呢&#xff1f;一般来说&#xff0c;我们使用javac命令将.java文件编译成.class文件&#xff0c;也就是Java字节码文件&#xff0c;然后由JVM将字节码文件加…...

分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)

&#x1f38a;【数据结构与算法】专题正在持续更新中&#xff0c;各种数据结构的创建原理与运用✨&#xff0c;经典算法的解析✨都在这儿&#xff0c;欢迎大家前往订阅本专题&#xff0c;获取更多详细信息哦&#x1f38f;&#x1f38f;&#x1f38f; &#x1fa94;本系列专栏 -…...

Typescript 类 (class)

基本用法 (通过关键字 class) // 基本用法 class VueService {constructor() {} // 构造器 } 类的约束&#xff08;通过关键字 implements&#xff09; // 接口定义属性类型 interface VueProps {name: stringinit: () > void }// 约束类 class VueService implements Vue…...

KDZD程控超低频高压发生器

一、产品概述 本产品接合了现代数字变频技术&#xff0c;采用微机控制&#xff0c;升压、降压、测量、保护自动化。由于电子化&#xff0c;所以体积小重量轻、大屏幕液晶显示&#xff0c;清晰直观、且能显示输出波形、打印试验报告。 设计指标符合《电力设备专用测试仪器通用…...

【华为OD机试 2023最新 】 过滤组合字符串(C++)

文章目录 题目描述输入描述输出描述用例题目解析C++题目描述 数字0、1、2、3、4、5、6、7、8、9分别关联 a~z 26个英文字母。 0 关联 “a”,”b”,”c”1 关联 “d”,”e”,”f”2 关联 “g”,”h”,”i”3 关联 “j”,”k”,”l”4 关联 “m”,”n”,”o”5 关联 “p”,”q”…...

Java笔记034-坦克大战【2】

目录 坦克大战【2】 线程-应用到坦克大战 坦克大战0.3 思路分析&#xff1a; 代码实现&#xff1a; 坦克大战0.4 增加功能 特别说明 思路分析&#xff1a; 代码实现&#xff1a; 坦克大战0.5 增加功能 思路分析&#xff1a; 代码实现&#xff1a; 坦克大战【2】 …...

【算法】【数组与矩阵模块】桶排序思想解决无序数组排序后相邻数间的最大差值

目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言 当前所有算法都使用测试用例运行过&#xff0c;但是不保证100%的测试用例&#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识&#xff01; 问题介绍 …...

C语言—函数

函数库函数自定义函数函数的参数函数的调用函数的嵌套调用和链式访问函数的声明和定义函数递归递归与迭代函数递归的经典题目维基百科&#xff08;台湾方面维护的&#xff0c;翻译形式跟大陆有所差异&#xff09;中对函数的定义&#xff1a;子程序在计算机科学中&#xff0c;子…...

Autosar模式管理实战系列03-基于Davinci工具的WDGM配置

本文框架 前言1.WdgMConfigSet 配置2. 新建监控实体(SE)2.1 新建检测点(Checkpoint)2.2 设置 WdgMInternalTransitions3. WdgMLocalStatusParams配置4. WdgMAliveSupervision配置5. 代码插入指导前言 前面我们介绍了WdgM(看门狗管理)是一个 AutoSAR 的基础模块,负责管理看门…...

AutoML-sklearn and torch

一、auto-sklearn 1.1 环境依赖 额外安装swig 第三方库 linux 支持, mac&#xff0c;windows不支持 1.2 示例代码 time_left_for_this_task 设定任务最大时间 per_run_time_limit 每个子任务最大训练时间 include 可以限制任务训练的模型 import autosklearn.classific…...

《扬帆优配》算力概念股大爆发,主力资金大扫货

3月22日&#xff0c;9股封单金额超亿元&#xff0c;工业富联、鸿博股份、鹏鼎控股分别为3.01亿元、2.78亿元、2.37亿元。 今日三大指数团体收涨&#xff0c;收盘共34股涨停&#xff0c;首要集中于数字经济方向&#xff0c;其间云核算、CPO大迸发。除去5只ST股&#xff0c;算计2…...

机械臂+底盘三维模型从solidworks到moveit配置功能包

文章目录 导出底盘STEP加载机械臂模型组合机械臂和底盘三维模型导出URDF在moveit中进行配置新建工作目录设置ROS工作空间的环境变量进入moveit setup加载URDF文件self-CollisionsPlanning groupsRobot posesControllersSimulationAuthor information生成配置包在rviz中进行可视…...

高并发系统设计:缓存、降级、限流、(熔断)

高并发系统设计&#xff1a;缓存、降级、限流、(熔断) 在开发高并发系统时有三把利器用来保护系统&#xff1a;缓存、降级和限流。 非核心服务可以采用降级、熔断&#xff0c;核心服务采用缓存和限流&#xff08;隔离流量可以最大限度的保障业务无损&#xff09;。 缓存 缓…...

《辉煌优配》放量大涨,A股成交额重回万亿!PCB板块继续领跑

多只绩优PCB概念股超跌。 今日A股放量反弹&#xff0c;成交额从头站上万亿关口。芯片板块掀涨停潮&#xff0c;景嘉微、芯原股份20cm涨停&#xff0c;紫光国微、兆易创新、跃岭股份等封板&#xff1b;AI算力、存储器、光模块、云核算等板块全线拉升&#xff0c;板块内个股再度批…...

Vue封装的过度与动画

动画效果 先把样式封装好&#xff0c;然后设置一个动画 不需要vue也能实现的动画的效果&#xff0c;我们只需要判断一下&#xff0c;然后动态的添加和删除类名即可 那能不能不自己写动态&#xff0c;就靠vue 首先我们要靠<transition>标签把需要动画的包裹起来 vue中…...

流量监控-ntopng

目录介绍安装使用介绍 ntopng是原始ntop的下一代版本&#xff0c;ntop是监视网络使用情况的网络流量探测器。ntopng基于libpcap&#xff0c;并且以可移植的方式编写&#xff0c;以便实际上可以在每个Unix平台&#xff0c;MacOSX和Windows上运行。 ntopng&#xff08;是的&…...

C++ 21 set容器

目录 一、set容器 1.1 简介 1.2 构造和赋值 1.3 大小和交换 1.4 插入和删除 1.5 查找和统计 1.6 set和multiset区别 1.7 内置类型指定排序规则 1.8 自定义数据类型指定排序规则 一、set容器 1.1 简介 ① set容器中所有元素在插入时自动被排序。 ② set容器和multise…...

什么是JWT

JSON Web Token&#xff08;缩写 JWT&#xff09;是目前最流行的跨域认证解决方案。 传统的session认证 http协议本身是一种无状态的协议&#xff0c;而这就意味着如果用户向我们的应用提供了用户名和密码来进行用户认证&#xff0c;那么下一次请求时&#xff0c;用户还要再一…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...