当前位置: 首页 > 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…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...