目录题目思路Code题目题目内容有一块 n×m4≤n,m≤50的矩形巧克力每个格子有一个正整数权值权值 ≤1000代表这一格的坚果数量。必须沿着格子横切恰好 3 刀、竖切恰好 3 刀将巧克力分成 4×416 块分给 16 个人。切分难以保证每个人分到的一样多因此你想照顾那个分得最少的人请通过合理安排切分方式使这个“分得最少的人”分到的坚果数量在所有切分方式中最多即求一种划分方式最大化这 16 块中权值和最小的那一块的权值和请输出这个最大化的最小权值和。输入描述第一行输入整数 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 的权值思路整体思路最小块权值和 T 具有单调性二分答案行切分在 C(n-1,3) 种方案里枚举列切分利用各行组前缀和的单调性贪心判定。1. 答案具有单调性若最小块和能达到 T则必然能达到 T-1。因此可以二分答案 T判定是否存在一种切法使 16 块全部 ≥ T。2. 枚举行切分从 n-1 个行间隙中选 3 个C(n-1,3) ≤ 18424 种。行组固定后第 i 个行组在第 c 列前的累计和 G_i[c] 可以由二维前缀和 O(1) 求出且 G_i 随 c 单调不减权值均为正。3. 判定 T需要选 3 个列切点 c1c2c3把列分成 4 段要求对每个行组 i、每段 [c_{j-1}, c_j]都有 G_i[c_j]-G_i[c_{j-1}] ≥ T。贪心逐段推进每个切点取各行组能满足 T 的最早位置的最大值。正确性G_i 单调不减 ⇒ 最早可行位置随起点单调不减早切不会使后续更难可交换归纳证明若存在可行切法贪心必成功。4. 对每个行切分二分出其能达到的最大 T取所有行切分的最大值。CodeJavaimport java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.List; public class Solution { static int n, m; // 行数、列数 static long[][] p; // 二维前缀和p[i][j] 前 i 行前 j 列总权值 static long[][] g new long[4][]; // g[i][c]第 i 个行组前 c 列累计和单调不减 /** 在 g[i] 的 [lo, m] 区间找最小 x 使 g[i][x] target等价 lower_bound */ static int lowerBoundRow(int i, int lo, long target) { int l lo, r m 1; // 搜索区间 [l, r) while (l r) { int mid (l r) 1; if (g[i][mid] target) l mid 1; else r mid; } return l; // 可能返回 m1 表示不存在 } /** 贪心判定能否选 3 个列切点使 16 块全部 ≥ T逐段推进详见文件头说明 */ static boolean feasible(long T) { int c 0; for (int seg 0; seg 3; seg) { // 前 3 段各选一个切点 int nxt c; for (int i 0; i 4; i) { int x lowerBoundRow(i, c 1, g[i][c] T); if (x m) return false; // 该行组整列凑不够 T if (x nxt) nxt x; } c nxt; // 切点推进到最晚需求处 } for (int i 0; i 4; i) { // 第 4 段剩余量都要 ≥ T if (g[i][m] - g[i][c] T) return false; } return true; } /** 从全部输入中按顺序解析整数跳过 [ ] , 等非数字字符 */ static ListLong parseInts(InputStream in) throws IOException { ListLong nums new ArrayList(); int ch; long cur 0; boolean inNum false; while ((ch in.read()) ! -1) { if (ch 0 ch 9) { cur cur * 10 (ch - 0); inNum true; } else { if (inNum) { nums.add(cur); cur 0; inNum false; } } } if (inNum) nums.add(cur); return nums; } public static void main(String[] args) throws IOException { ListLong nums parseInts(System.in); if (nums.size() 2) return; n nums.get(0).intValue(); m nums.get(1).intValue(); // ---------- 二维前缀和 ---------- p new long[n 1][m 1]; for (int i 0; i n; i) for (int j 0; j m; j) p[i 1][j 1] p[i 1][j] p[i][j 1] - p[i][j] nums.get(2 i * m j); long ans 0; // ---------- 枚举全部行切分3 个切点 1..n-1ijk ---------- for (int a 1; a 2 n - 1; a) for (int b a 1; b 1 n - 1; b) for (int c b 1; c n - 1; c) { int[] rows {0, a, b, c, n}; // 计算 4 个行组的累计和数组 g并求二分上界最小行组和/4 long up -1; for (int i 0; i 4; i) { g[i] new long[m 1]; for (int col 0; col m; col) g[i][col] p[rows[i 1]][col] - p[rows[i]][col]; long h g[i][m] / 4; if (up 0 || h up) up h; } // ---------- 二分该行切分下的最大可达 T ---------- long lo 1, best 0; while (lo up) { long mid (lo up) / 2; if (feasible(mid)) { best mid; lo mid 1; } else up mid - 1; } ans Math.max(ans, best); } System.out.println(ans); } }Gopackage main import ( fmt io os ) var n, m int var p [55][55]int64 // 二维前缀和p[i][j] 前 i 行前 j 列总权值 var g [4][55]int64 // g[i][c]第 i 个行组前 c 列累计和单调不减 // 手写二分等价 lower_bound在 g[i] 的 [lo, m] 中找最小 x 使 g[i][x] target func lowerBoundRow(i, lo int, target int64) int { l, r : lo, m1 // 搜索区间 [l, r) for l r { mid : (l r) / 2 if g[i][mid] target { l mid 1 } else { r mid } } return l // 可能返回 m1 表示不存在 } // 贪心判定能否选 3 个列切点使 16 块全部 ≥ T逐段推进详见文件头说明 func feasible(T int64) bool { c : 0 for seg : 0; seg 3; seg { // 前 3 段各选一个切点 nxt : c for i : 0; i 4; i { x : lowerBoundRow(i, c1, g[i][c]T) if x m { // 该行组整列凑不够 T return false } if x nxt { nxt x } } c nxt // 切点推进到最晚需求处 } for i : 0; i 4; i { // 第 4 段剩余量都要 ≥ T if g[i][m]-g[i][c] T { return false } } return true } // 从全部输入中按顺序解析整数跳过 [ ] , 等非数字字符 func parseInts(data []byte) []int64 { var nums []int64 i : 0 for i len(data) { if data[i] 0 data[i] 9 { var v int64 for i len(data) data[i] 0 data[i] 9 { v v*10 int64(data[i]-0) i } nums append(nums, v) } else { i } } return nums } func imax(a, b int64) int64 { if a b { return a } return b } func main() { data, _ : io.ReadAll(os.Stdin) nums : parseInts(data) if len(nums) 2 { return } n int(nums[0]) m int(nums[1]) // ---------- 二维前缀和 ---------- for i : 0; i n; i { for j : 0; j m; j { p[i1][j1] p[i1][j] p[i][j1] - p[i][j] nums[2i*mj] } } var ans int64 // ---------- 枚举全部行切分3 个切点 1..n-1ijk ---------- for a : 1; a2 n-1; a { for b : a 1; b1 n-1; b { for c : b 1; c n-1; c { rows : [5]int{0, a, b, c, n} // 计算 4 个行组的累计和数组 g并求二分上界最小行组和/4 up : int64(-1) for i : 0; i 4; i { for col : 0; col m; col { g[i][col] p[rows[i1]][col] - p[rows[i]][col] } h : g[i][m] / 4 if up 0 || h up { up h } } // ---------- 二分该行切分下的最大可达 T ---------- lo, best : int64(1), int64(0) for lo up { mid : (lo up) / 2 if feasible(mid) { best mid lo mid 1 } else { up mid - 1 } } ans imax(ans, best) } } } fmt.Println(ans) }C#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAXN 55 static int n, m; /* 行数、列数 */ static long long P[MAXN][MAXN]; /* 二维前缀和P[i][j]前i行前j列总权值 */ static long long G[4][MAXN]; /* G[i][c]第 i 个行组前 c 列累计和单调不减 */ /* 从标准输入读入全部内容按顺序解析出整数忽略所有非数字字符 */ static int read_all(long long *out, int cap) { int cnt 0; long long cur 0; int in_num 0, sign 1; int ch; while ((ch getchar()) ! EOF) { if (isdigit((unsigned char)ch)) { cur cur * 10 (ch - 0); in_num 1; } else if (ch - !in_num) { sign -1; /* 负号本题权值为正防御性支持 */ } else { if (in_num) { if (cnt cap) out[cnt] sign * cur; cur 0; in_num 0; sign 1; } } } if (in_num cnt cap) out[cnt] sign * cur; return cnt; } /* 手写二分等价 lower_bound在 G[i] 的 [lo, m] 中找最小 x 使 G[i][x] target */ static int lower_bound_row(int i, int lo, long long target) { int l lo, r m 1; /* 搜索区间 [l, r) */ while (l r) { int mid (l r) / 2; if (G[i][mid] target) l mid 1; else r mid; } return l; /* 可能返回 m1 表示不存在 */ } /* 贪心判定能否选 3 个列切点使 16 块全部 ≥ T逐段推进详见文件头说明 */ static int feasible(long long T) { int c 0; for (int seg 0; seg 3; seg) { int nxt c; for (int i 0; i 4; i) { int x lower_bound_row(i, c 1, G[i][c] T); if (x m) return 0; /* 该行组整列凑不够 T */ if (x nxt) nxt x; } c nxt; } for (int i 0; i 4; i) if (G[i][m] - G[i][c] T) return 0; /* 第 4 段剩余不足 */ return 1; } /* 取三者最大/最小的辅助函数C 标准库无内置 min/max */ static long long lmin(long long a, long long b) { return a b ? a : b; } static long long lmax(long long a, long long b) { return a b ? a : b; } int main(void) { /* 最多 2 50*50 2502 个整数开 3000 足够 */ static long long vals[3000]; int cnt read_all(vals, 3000); if (cnt 2) return 0; n (int)vals[0]; m (int)vals[1]; /* ---------- 二维前缀和 ---------- */ for (int i 0; i n; i) for (int j 0; j m; j) P[i 1][j 1] P[i 1][j] P[i][j 1] - P[i][j] vals[2 i * m j]; long long ans 0; /* ---------- 枚举全部行切分3 个切点 1..n-1ijk ---------- */ for (int a 1; a 2 n - 1; a) for (int b a 1; b 1 n - 1; b) for (int c b 1; c n - 1; c) { int rows[5] {0, a, b, c, n}; /* 计算 4 个行组的累计和数组 G并求二分上界最小行组和/4 */ long long up -1; for (int i 0; i 4; i) { for (int col 0; col m; col) G[i][col] P[rows[i 1]][col] - P[rows[i]][col]; long long h G[i][m] / 4; if (up 0 || h up) up h; } /* ---------- 二分该行切分下的最大可达 T ---------- */ long long lo 1, best 0; while (lo up) { long long mid (lo up) / 2; if (feasible(mid)) { best mid; lo mid 1; } else up mid - 1; } ans lmax(ans, best); } printf(%lld\n, ans); return 0; }【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。