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

LeetCode:3218. 切蛋糕的最小总开销 I(贪心 Java)

目录

3218. 切蛋糕的最小总开销 I

题目描述:

实现代码与解析:

贪心

原理思路:


3218. 切蛋糕的最小总开销 I

题目描述:

        有一个 m x n 大小的矩形蛋糕,需要切成 1 x 1 的小块。

给你整数 m ,n 和两个数组:

  • horizontalCut 的大小为 m - 1 ,其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
  • verticalCut 的大小为 n - 1 ,其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中,你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一:

  1. 沿着水平线 i 切开蛋糕,开销为 horizontalCut[i] 。
  2. 沿着垂直线 j 切开蛋糕,开销为 verticalCut[j] 。

每次操作后,这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销,并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

示例 1:

输入:m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出:13

解释:

  • 沿着垂直线 0 切开蛋糕,开销为 5 。
  • 沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
  • 沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
  • 沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。
  • 沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。

总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2:

输入:m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出:15

解释:

  • 沿着水平线 0 切开蛋糕,开销为 7 。
  • 沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。
  • 沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。

总开销为 7 + 4 + 4 = 15 。

提示:

  • 1 <= m, n <= 20
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 103

实现代码与解析:

贪心

import java.util.Arrays;class Solution {public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {Arrays.sort(horizontalCut);Arrays.sort(verticalCut);int rs = m - 2, cs = n - 2;int cntR = 1; // 本次横向需要切的次数int cntC = 1; // 本次纵向需要切的次数int res=  0;while (rs >= 0 || cs >= 0) {if ( cs < 0 || (rs >= 0 && horizontalCut[rs] > verticalCut[cs])) { // 横向切res += horizontalCut[rs--] * cntC;cntR++;} else if (rs < 0 || (cs >= 0 && horizontalCut[rs] <= verticalCut[cs])) { // 纵向切res += verticalCut[cs--] * cntR;cntC++;}}return res;}
}

原理思路:

        因为无论如何每块的行与列都需要被切,所以每行和列开销最大的需要切的块数越少那么总开销就越少,所以每次切到时候选行和列中开销最大的行切即可。

相关文章:

LeetCode:3218. 切蛋糕的最小总开销 I(贪心 Java)

目录 3218. 切蛋糕的最小总开销 I 题目描述&#xff1a; 实现代码与解析&#xff1a; 贪心 原理思路&#xff1a; 3218. 切蛋糕的最小总开销 I 题目描述&#xff1a; 有一个 m x n 大小的矩形蛋糕&#xff0c;需要切成 1 x 1 的小块。 给你整数 m &#xff0c;n 和两个数…...

前端下载后端文件流,文件可以下载,但是打不开,显示“文件已损坏”的问题分析与解决方案

目录 场景还原 相关代码开发者工具 - 网络请求记录 问题排查 定位改bug 总结 场景还原 我在前端使用axios接收后端xlsx表格文件流并下载&#xff0c;xlsx文件能够下载成功&#xff0c;但是打开却显示文件无法打开 相关代码 请求API封装:Content–Type以及responseType经核…...

PageRank Web页面分级算法 HNUST【数据分析技术】(2025)

1.理论知识 算法原理PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级。 Google 把从 A 页面到 B 页面的链接解释为A页面给B页面投票&#xff0c; Google 根据投票来源&#xff08;甚至来源的来源&#xff0c; 即链接到A页面的页面&#xff09;和投票目标的等级来决定新…...

数字IC前端学习笔记:脉动阵列的设计方法学(四)

相关阅读 数字IC前端https://blog.csdn.net/weixin_45791458/category_12173698.html?spm1001.2014.3001.5482 引言 脉动结构&#xff08;也称为脉动阵列&#xff09;表示一种有节奏地计算并通过系统传输数据的处理单元(PEs)网络。这些处理单元有规律地泵入泵出数据以保持规则…...

对话 Project Astra 研究主管:打造通用 AI 助理,主动视频交互和全双工对话是未来重点

Project Astra 愿景之一&#xff1a;「系统不仅能在你说话时做出回应&#xff0c;还能在持续的过程中帮助你。」 近期&#xff0c;Google DeepMind 的 YouTube 频道采访了 Google DeepMind 研究主管格雷格韦恩 (Greg Wayne)。 格雷格韦恩的研究工作为 DeepMind 的诸多突破性成…...

NetApp 存储设备巡检作业指导书

NetApp 存储设备巡检作业指导书 一、目的 本指导书旨在指导管理员通过 SSH 或 Console 登录 NetApp FAS2552 存储系统&#xff0c;切换节点并进行日常管理操作。 二、适用范围 适用于基于 NetApp ONTAP 操作系统的 FAS2552 存储环境。 三、前提条件 网络和权限要求&#xff1…...

adb无法连接到安卓设备【解决方案】报错:adb server version (40) doesn‘t match this client (41);

下载老版本Platformtools​​​​​​​​​​​​​​https://dl.google.com/android/repository/platform-tools_r28.0.2-windows.zip?hlzh-cn 替换原来的platform-tools文件夹即可。 问题原因分析&#xff1a;电脑端adb client版本&#xff08;41&#xff09;和安卓端adb …...

每天五分钟机器学习:核函数

本文重点 在学习支持向量机算法之前,我们要继续学习一些数学基础,本文我们将学习核函数的概念。当数据线性不可分的时候,此时就需要核函数出场了,它可以将低维不可分的数据映射到高维可分数据,此时就可以完成数据分类了。 核函数的定义 核函数K(x, y)定义为两个数据点x…...

Word窗体联动Excel实现级联组合框

在Word中的使用用户窗体&#xff08;UserForm&#xff09;定制界面如下图所示&#xff0c;其中控件如下&#xff08;忽略Label控件&#xff09;&#xff1a; CompanyName 组合框Attention 组合框CommandButton1 按钮 现在需要实现级联组合框效果&#xff0c;即用户在 CompanyN…...

RAG实战:构建基于本地大模型的智能问答系统

RAG实战&#xff1a;构建基于本地大模型的智能问答系统 引言 在当今AI快速发展的时代&#xff0c;如何构建一个既智能又可靠的问答系统是一个重要课题。本文将介绍如何使用RAG&#xff08;检索增强生成&#xff09;技术&#xff0c;结合本地大模型&#xff0c;构建一个高效的智…...

Docker 部署 plumelog 最新版本 实现日志采集

1.配置plumelog.yml version: 3 services:plumelog:#此镜像是基于plumelog-3.5.3版本image: registry.cn-hangzhou.aliyuncs.com/k8s-xiyan/plumelog:3.5.3container_name: plumelogports:- "8891:8891"environment:plumelog.model: redisplumelog.queue.redis.redi…...

TCP/IP 邮件

TCP/IP邮件是互联网通信中非常重要的应用之一。当我们发送电子邮件时&#xff0c;我们实际上并没有直接使用TCP/IP协议&#xff0c;而是通过电子邮件程序&#xff0c;例如微软的Outlook、莲花软件的Notes或Netscape Communicator等来实现。这些电子邮件程序背后使用了不同的TCP…...

FreeSql

官网 实体特性 Ado 它包括所有对 SQL 操作的封装&#xff0c;提供 ExecuteReader、ExecuteDataSet、ExecuteDataTable、ExecuteNonQuery、ExecuteScalar 等方法&#xff0c;使用起来和传统 SqlHelper 一样。 1、安装包 Install-Package FreeSql Install-Package FreeSql.Prov…...

记一次前端Vue项目国际化解决方案

背景 有一个vue项目&#xff0c;要实现国际化功能&#xff0c;能够切换中英文显示&#xff0c;因为该项目系统的用户包括了国内和国外用户。 需求 1、页面表单上的所有中文标签要国际化&#xff0c;包括表单属性标签、表格列头标签等&#xff0c; title“数量”&#xff1b;…...

JS进阶-手写Promise

一、什么是Promise 在Promise A规范中规定&#xff0c;Promise是一个有一个符合规范的then方法的对象或者函数。 1.关于then then接收onFulfilled和onRejected两个可选参数&#xff1b;then必须返回一个新的Promise对象&#xff1b;如果onFulfilled是一个函数 在状态切换为f…...

PCL点云库入门——PCL库点云滤波算法之直通滤波(PassThrough)和条件滤波(ConditionalRemoval)

0、滤波算法概述 PCL点云库中的滤波算法是处理点云数据不可或缺的一部分&#xff0c;它们能够有效地去除噪声、提取特征或进行数据降维。例如&#xff0c;使用体素网格滤波&#xff08;VoxelGrid&#xff09;可以减少点云数据量&#xff0c;同时保留重要的形状特征。此外&#…...

ioctl回顾

一、ioctl协议的命令组成 cmd本质为一个32位的数字&#xff0c;共分为四段&#xff1a; [31-30]:读写方向dir&#xff0c;分为无数据(_IO)、读数据(_IOR)、写数据(_IOW)、读写数据(_IOWR)四种模式&#xff1b; [29-16]:传递数据的大小size&#xff0c;一般利用其宏_IO、_IOR…...

jquery-validate在前端数据校验中的应用以及remote异步调用实践-以若依为例

目录 前言 一、关于Jquery Validate组件 1、validate是什么 2、内置验证方式及触发方式 3、自定义验证规则 二、基本验证实战以及Remote验证 1、基本验证实现 2、remote校验方式 三、总结 前言 随着技术的不断演进&#xff0c;在我们的日常开发过程中&#xff0c;大家一…...

如何重新设置VSCode的密钥环密码?

故障现象&#xff1a; 忘记了Vscode的这个密码&#xff1a; Enter password to unlock An application wants access to the keyring “Default ke... Password: The unlock password was incorrect Cancel Unlock 解决办法&#xff1a; 1.任意terminal下&#xff0c;输入如下…...

Android--java实现手机亮度控制

文章目录 1、开发需求2、运行环境3、主要文件4、布局文件信息5、手机界面控制代码6、debug 1、开发需求 需求&#xff1a;开发一个Android apk实现手机亮度控制 2、运行环境 Android studio最新版本 3、主要文件 app\src\main\AndroidManifest.xml app\src\main\res\layou…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...