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

44. 开发商购买土地

44. 开发商购买土地

前缀和

思路
可能的情况有两类,A占前 i 行,B占剩余行;A占前 j 列,B占剩余列。
若直接暴力枚举,第一层 for 循环遍历行(控制行的切分),第二层、第三层 for 循环计算A区域中元素和,时间复杂度O(n^3)。
1、计算每行的和,得到行前缀和数组horizontoal,horizontoal[i]表示第i行元素和,
计算每列的和,得到列前缀和数组vertical,vertical[j]表示第j行元素和。
2、枚举按行切分的情况,计算差值,
枚举按列切分的情况,计算差值。
时间复杂度O(n^2)

import java.util.Scanner;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int sum = 0;int[][] vec = new int[n][m];// 初始化并计算数组元素和for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {vec[i][j] = scanner.nextInt();sum += vec[i][j];}}// 行前缀和int[] horizontoal = new int[n];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {horizontoal[i] += vec[i][j];}}// 列前缀和int[] vertical = new int[m];for (int j = 0; j < m; j++) {for (int i = 0; i < n; i++) {vertical[j] += vec[i][j];}}int res = Integer.MAX_VALUE;// 水平切分int horizontoalCut = 0; // 前 i 行元素的和for (int i = 0; i < n; i++) {horizontoalCut += horizontoal[i];res = Math.min(res, Math.abs(horizontoalCut - (sum - horizontoalCut)));}// 垂直切分 int verticalCut = 0; // 前 j 列元素的和for (int j = 0; j < m; j++) {verticalCut += vertical[j];res = Math.min(res, Math.abs(verticalCut - (sum - verticalCut)));}System.out.println(res);scanner.close();}
}

进阶

前缀和(优化)

http://www.hskmm.com/?act=detail&tid=30242

相关文章:

  • 当AI与机器人走进生活:我们即将迎来的日常变革
  • 显微镜厂家TOP10推荐:拓界光电以创新技术引领精密观测新时代
  • net中使用了垃圾回收机制(GC)功能
  • 2025 超景深三维显微镜厂家 TOP10 推荐:三维成像技术的行业应用标杆​
  • 音乐节奏跳动
  • CF2160 Codeforces Round 1058 (Div. 2) 游记
  • 2025年国内铝单板工厂推荐/国内铝单板厂家/ 市场铝单板推/公司榜荐
  • 一个老码农的掏心窝推荐:微擎,我后悔没早点遇到的开发利器
  • 国内铝单板工厂推荐/国内铝单板厂家/ 市场铝单板推荐:四川汇才铝业有限公司
  • 超景深显微镜厂家TOP10推荐:拓界光电引领精密观测新时代
  • 2025 闪蒸/流化床/喷雾/实验型喷雾/离心喷雾/压力喷雾/流化床喷雾/桨叶/盘式/真空耙式干燥机厂家推荐榜单:技术适配与场景落地能力成核心考量
  • 2025 年点胶机源头厂家最新推荐排行榜:自动 / 果冻胶 / 无痕内衣 / 烫钻 / 珠宝热熔胶等多类型设备优质企业精选
  • harbor 局域网https 自签名证书搭建
  • HyperWorks许可证使用报告生成
  • 2025年国内铝单板工厂推荐/国内铝单板厂家/ 市场铝单板推/公司权威排行榜荐
  • 小程序 拖动节点
  • ORA-00604: 递归 SQL 级别 1 出现错误 ORA-01000: 超出打开游标的最大数
  • Python的解释器
  • 10月13号
  • shiro快速启动
  • netty思维导图总结
  • gitreset、revert
  • 2025 年直流电弧炉厂商最新推荐排行榜:全面剖析优质企业技术实力与产品优势,助力各行业企业精准选购适配设备贵金属/节能直流/环保直流电弧炉厂家推荐
  • 2025 海外仓服务公司最新推荐榜单:含维修换标特色服务,三大优选品牌口碑解析美国/英国/德国/法国海外仓公司推荐
  • MaxKB 的 RAG 引擎和向量存储实现细节
  • 工业相机传感器CCD的原理及基础知识
  • ubuntu22.04安装激活Navicat15详细教程
  • 20232406 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 经验再多,可能不如有个OCP证书好使
  • 2025 国内三效废水/多效废水/母液/废液蒸发器及三效/多效/单效MVR蒸发器厂家精选指南