当前位置: 首页 > 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;}
}

原理思路:

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

http://www.lryc.cn/news/509637.html

相关文章:

  • 前端下载后端文件流,文件可以下载,但是打不开,显示“文件已损坏”的问题分析与解决方案
  • PageRank Web页面分级算法 HNUST【数据分析技术】(2025)
  • 数字IC前端学习笔记:脉动阵列的设计方法学(四)
  • 对话 Project Astra 研究主管:打造通用 AI 助理,主动视频交互和全双工对话是未来重点
  • NetApp 存储设备巡检作业指导书
  • adb无法连接到安卓设备【解决方案】报错:adb server version (40) doesn‘t match this client (41);
  • 每天五分钟机器学习:核函数
  • Word窗体联动Excel实现级联组合框
  • RAG实战:构建基于本地大模型的智能问答系统
  • Docker 部署 plumelog 最新版本 实现日志采集
  • TCP/IP 邮件
  • FreeSql
  • 记一次前端Vue项目国际化解决方案
  • JS进阶-手写Promise
  • PCL点云库入门——PCL库点云滤波算法之直通滤波(PassThrough)和条件滤波(ConditionalRemoval)
  • ioctl回顾
  • jquery-validate在前端数据校验中的应用以及remote异步调用实践-以若依为例
  • 如何重新设置VSCode的密钥环密码?
  • Android--java实现手机亮度控制
  • 原点安全再次入选信通院 2024 大数据“星河”案例
  • torch.nn.init 模块介绍
  • 人工智能与物联网:从智慧家居到智能城市的未来蓝图
  • 极狐GitLab 17.7正式发布,可从 GitLab 丝滑迁移至极狐GitLab【一】
  • 纯Dart Flutter库适配HarmonyOS
  • 【R语言遥感技术】“R+遥感”的水环境综合评价方法
  • 软件工程三 需求获取与结构化分析方法(需求分析、功能建模、数据建模、行为建模、数据字典等)
  • Python 抽象基类 ABC :从实践到优雅
  • Elasticsearch检索方案之一:使用from+size实现分页
  • 知识图谱+大模型:打造全新智慧城市底层架构
  • Flutter开发HarmonyOS 鸿蒙App的好处、能力以及把Flutter项目打包成鸿蒙应用