首页 > 试题广场 >

小红的蛋糕切割

[编程题]小红的蛋糕切割
  • 热度指数：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

说明

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

算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-03-31 13:45:08
题目链接 小红的蛋糕切割 题目描述 小红拿到了一个矩形的蛋糕，共分成了 行 列，共 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。 小红希望切割出一个正方形的小蛋糕（正方形边长必须平行于矩阵的边长，且必须都是完整的区域），自己吃掉正方形的部分，把剩下的部分给小紫吃。 小红希望 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 2023116256
发表于 2025-05-26 15:35:51
由于n，m<=1e3，所以直接枚举小红的所有吃法，从1到min(n,m)枚举小红蛋糕的边长，再枚举每个边长下小红蛋糕的左上角坐标，计算小红蛋糕和小紫蛋糕的美味度，并记录差值最小的答案。计算小红蛋糕和小紫蛋糕的美味度时可以使用二维前缀和预处理原数组，来减少时间复杂度。 #include<b 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-18 11:44:13
题目链接 小红的蛋糕切割 题目描述 小红有一个 的矩形蛋糕，每个区域都有一个美味度。 她希望切割出一个正方形的小蛋糕给自己吃，剩下的部分给小紫吃。 她希望两人吃的部分的美味度之和尽可能接近。设小红吃的美味度之和为 ，小紫吃的为 ，请你输出 的最小值。 解题思路 这是一个在矩阵中寻找最优子结构的问 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 梦想去阿里的冰棍
发表于 2025-09-04 20:48:34
先说说使用的算法：二维前缀和+二分+枚举 做法： 先求这个矩阵的二维前缀和 枚举这个矩阵的每个美味度点，且这个点是我们所求的正方形的右下脚末端点 由于是求正方形，且每个美味度都是正数，所以我们可以二分这个正方形的边长，边长越大，正方形美味度越大。我们只需要二分美味度总和到 就可以了。（sum是整 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 扎男_
发表于 2025-05-27 21:34:31
// 活动地址： 牛客春招刷题训练营 - 编程打卡活动 #include <ios> #pragma clang diagnostic push #pragma ide diagnostic ignored "cppcoreguidelines-narrowing-con 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 君鸿
发表于 2025-03-20 16:56:17
解题思路看到题目后，我们很容易得出一个结论：令所有蛋糕的美味度总和为sum。那么当s1越接近sum的一半，|s1 - s2|就越小。同时s1 + s2 = sum，故|s1 - s2| = |sum - s1 - s1|。本题的关键是求计算s1，即枚举所有正方形的美味度。将一维数组的前缀和扩展到二维 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

相关试题

小红的蛋糕切割

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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