首页 > 试题广场 >

小美的蛋糕切割

[编程题]小美的蛋糕切割

小美有一个矩形的蛋糕，共分成了 $n$ 行 $m$ 列，共 $n \times m$ 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。

小美希望两个人吃的部分的美味度之和尽可能接近，请你输出 $|s_1-s_2|$ 的最小值。（其中 $s_1$ 代表小美吃的美味度， $s_2$ 代表小团吃的美味度）。

请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。

第一行输出两个正整数  和  ，代表蛋糕区域的行数和列数。
接下来的  行，每行输入  个正整数  ，用来表示每个区域的美味度。

一个整数，代表  的最小值。

示例1

输入

2 3
1 1 4
5 1 4

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

算法知识视频讲解

暂无题解

来自：美团2023年秋招笔试...

难度：

16条回答 34收藏 1518浏览

小美的蛋糕切割

扫一扫，把题目装进口袋