9.26华为OD机试真题 新系统 – .坚果巧克力 (JavaPyCC++JsGo)
2026 华为OD机试真题9月26日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
有一块 $n \times m$（$4 \leq n, m \leq 50$）的矩形巧克力，每个格子有一个正整数权值（权值 $\leq 1000$），代表这一格的坚果数量。
必须沿着格子横切恰好 $3$ 刀、竖切恰好 $3$ 刀，将巧克力分成 $4 \times 4 = 16$ 块，分给 $16$ 个人。
切分难以保证每个人分到的一样多，因此你想照顾那个分得最少的人，请通过合理安排切分方式，使这个“分得最少的人”分到的坚果数量在所有切分方式中最多（即：求一种划分方式，最大化这 $16$ 块中权值和最小的那一块的权值和，请输出这个最大化的最小权值和。）
2026 华为OD机试真题9月26日华为OD上机新系统考试真题 100 分题型
输入描述
第一行输入整数 $n$，表示巧克力的行数。
第二行输入整数 $m$，表示巧克力的列数。
第三行输入一个 $n$ 行 $m$ 列的二维整数数组，格式为 [[a11,a12,...,a1m],[a21,...,a2m],...,[an1,...,anm]]，表示每个格子的坚果数量。
输出描述
输出一个整数，表示在最优切分方案下，$16$ 块巧克力中权值和最小的那一块所能达到的最大权值和。
示例1
输入
4
7
[[2,1,1,1,2,1,1],[2,2,2,2,2,2,2],[1,2,3,4,5,6,7],[7,6,5,4,3,2,1]]输出
2说明
- 只有四行，只能每行都分开
- 第一行最紧张，$7$ 格子分 $4$ 块，一定会有一块只能分到 $1$ 格，选择第一列的 $2$ 分得 $1$ 格，会导致第三行第一列的和只有 $1$，因此想要获得超过 $1$ 的结果只能选择第 $5$ 列前后进行划分
- 在这个基础上，一种可行的划分方式是：
- 第 $1$ 行：
2,1|1,1|2|1,1- 第 $2$ 行：
2,2|2,2|2|2,2- 第 $3$ 行：
1,2|3,4|5|6,7- 第 $4$ 行：
7,6|5,4|3|2,1- 此时第 $1$ 行的
|1,1|、|2|、|1,1|三块为最小，但是都有 $2$ 的权值和
示例2
输入
5
6
[[1,1,1,5,5,5],[1,1,1,1,1,1],[6,6,6,6,6,6],[6,6,6,6,6,6],[6,6,6,6,6,6]]输出
6说明
- 一种可行的划分是：
- 第 $1$ 行：
1,1,1|5|5|5- 第 $2$ 行：
1,1,1|1|1|1- 第 $3$ 行：
6,6,6|6|6|6- 第 $4$ 行：
6,6,6|6|6|6- 第 $5$ 行：
6,6,6|6|6|6- 这种划分保障了在正确划分的基础上左上角至少获得了 $6$ 的权值
解题思路
本题采用【二分答案 + 枚举切线 + 贪心】算法：最终答案越小越容易满足，因此“能否让 16 块的权值和都不少于 target”具有单调性，可以在 到全部坚果总数除以 16 的范围内二分最大答案。
固定三条横向切线后，巧克力被分为四个横条。随后从左到右累计当前列在四个横条中的权值；只要四个累计值都达到 target，就立即切出一个竖向区域并重新累计。因为所有格子权值均为正数，尽早切割会给后续区域留下最多的列，因此这种贪心方式能够得到最多的合法竖向区域。只要可以切出至少四个区域，剩余列并入最后一块也不会降低其权值和。
通过按列建立纵向前缀和，可以在常数时间内得到某一列在四个横条中的权值。实现还会比较“枚举三条横切线”和“枚举三条竖切线”的预计代价；如果枚举竖切线更少，就先转置矩阵，从而降低枚
