京东 · 穷举 · 算法编程题
京东 穷举 n ≤ 1e3 时限 1 秒 / 256 MB

题目描述

小红拿到了一个矩形的蛋糕，共分成了 n 行 m 列，共 n*m 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。
小红希望切割出一个正方形的小蛋糕（正方形边长必须平行于矩阵的边长，且必须都是完整的区域），自己吃掉正方形的部分，把剩下的部分给小紫吃。
小红希望两人吃的部分的美味度之和尽可能接近，小红吃的蛋糕美味度之和为 s_1 ，小紫吃的蛋糕美味度之和为 s_2 ，请你输出 |s_1-s_2| 的最小值。

输入输出

输入描述
第一行输出两个正整数 n 和 m ，代表蛋糕区域的行数和列数。
接下来的 n 行，每行输入 m 个正整数 a_ij ，用来表示每个区域的美味度。
1≤ n,m ≤ 10^3
1≤ a_i ≤ 10^4
输出描述
一个整数，代表 |s_1-s_2| 的最小值。

样例共 1 组

样例 1 · 如下图，红色部分为小红食用的部分。
输入
3 3
1 2 3
2 3 4
3 2 1
输出
1

算法解析依据充分

考点：数组 · 穷举 · 前缀和

数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e3，m ≤ 1e3
  • 元素值域：a_i ≤ 1e4（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：穷举

把候选答案空间全部列出来逐一检验，靠数据范围小来兜底。

思路框架（穷举 通法 · 非本题专属）

  1. 确定枚举什么（下标区间 / 子集 / 数值）。
  2. 用一层或多层循环（或递归）生成所有候选。
  3. 对每个候选判断是否满足题目条件，满足就统计或更新最优值。
  4. 先按数据范围估算枚举量，确认不会超时。

实现要点：多重循环是最直接的写法；枚举组合时可用递归 + 回溯，或用位掩码代表子集。

复杂度：时间 O(候选数 × 单次校验代价) ｜ 空间 O(1)

该范式的通法易错点

  • 没先估复杂度，枚举量超出时限（这是最常见的超时原因）。
  • 去重没做好，同一种方案被多次统计。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 3 / 1 2 3 / 2 3 4 / 3 2 1 → 输出 1

如下图，红色部分为小红食用的部分。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第四批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解