首页 > 试题广场 >

小红的蛋糕切割

[编程题]小红的蛋糕切割
  • 热度指数：280 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了一个矩形的蛋糕，共分成了n行m列，共n*m个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。
小红希望切割出一个正方形的小蛋糕（正方形边长必须平行于矩阵的边长，且必须都是完整的区域），自己吃掉正方形的部分，把剩下的部分给小紫吃。
小红希望两人吃的部分的美味度之和尽可能接近，小红吃的蛋糕美味度之和为 s_1，小紫吃的蛋糕美味度之和为 s_2，请你输出|s_1-s_2|的最小值。

输入描述:
第一行输出两个正整数n和m，代表蛋糕区域的行数和列数。
接下来的n行，每行输入m个正整数a_{ij}，用来表示每个区域的美味度。
1\leq n,m \leq 10^3
1\leq a_i \leq 10^4


输出描述:
一个整数，代表|s_1-s_2|的最小值。
示例1

输入

3 3
1 2 3
2 3 4
3 2 1

输出

1

说明

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

算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

数组 前缀和 穷举
难度：
0条回答 40浏览

热门推荐

相关试题

小红的蛋糕切割

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号