美团 · 计算几何 · 算法编程题
美团 计算几何 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_ij ≤ 10^4
输出描述
一个整数，代表 |s_1-s_2| 的最小值。

样例共 1 组

样例 1 · 把蛋糕像这样切开： 1 1 | 4 5 1 | 4 左边蛋糕美味度之和是8 右边蛋糕美味度之和是8 所以答案是0。
输入
2 3
1 1 4
5 1 4
输出
0

算法解析依据一般

考点：计算几何

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

题目画像

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

解题思路

参考方向：计算几何

把几何关系转成坐标运算，用整数运算避免浮点误差。

思路框架（计算几何 通法 · 非本题专属）

  1. 把点、向量、线段用坐标表示。
  2. 几何判定（平行、垂直、共线、相交）尽量用叉积/点积的整数形式：叉积为 0 即共线。
  3. 距离用平方比较，避免开方带来的浮点误差。
  4. 面积用叉积（鞋带公式）计算。

实现要点：叉积 cross = x1*y2 - x2*y1；用它判断顺时针/逆时针和共线。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系（应用整数叉积）。
  • 没考虑三点共线、重合等退化情况。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

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

把蛋糕像这样切开：

1 1 | 4

5 1 | 4

左边蛋糕美味度之和是8

右边蛋糕美味度之和是8

所以答案是0。

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

本题来源：2023年美团秋招编程岗第一批笔试。

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