描述

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

小美希望两个人吃的部分的美味度之和尽可能接近，请你输出∣s1​−s2​∣的最小值。（其中s1​代表小美吃的美味度，s2​代表小团吃的美味度）。

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

输入描述：

第一行输出两个正整数 n 和 m ，代表蛋糕区域的行数和列数。
接下来的 n 行，每行输入 m 个正整数 aij​ ，用来表示每个区域的美味度。
2≤n,m≤10^3
1≤aij​≤10^4

输出描述：

一个整数，代表 ∣s1​−s2​∣ 的最小值。

示例1

输入：

2 3
1 1 4
5 1 4

输出：

0

说明：

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

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.有一块蛋糕被分为n行m列

2.每一个坐标有一个美味度

3.现在希望切一刀，使得两块蛋糕的美味度之和的差的绝对值尽量小

4.问最小的美味度之和的差值的绝对值是多少

二、解题思路

1.首先读取数据到matrix[n][m]

2.维护一个二维前缀和数组matrixsum[n][m]表示从0，0到i，j的面积大小(可以使用同一个数组）

3.分别模拟横切和竖切蛋糕，并记录美味度之和之差的绝对值的最小值

4.比较最小值，返回最小值

三、具体步骤

使用的语言是C

#include <stdio.h>
#define ll long long
int main() {ll n, m, i, j;if (scanf("%lld %lld", &n, &m) != EOF) {ll ma[n + 1][m + 1];for(i = 0; i <= n; i++) {for(j = 0; j <= m; j++) {ma[i][j] = 0;}}// 遍历蛋糕的每一块，并记录前缀和for(i = 1; i <= n; i++) {for(j = 1; j <= m; j++) {if(scanf("%lld", &ma[i][j]) != EOF) {ma[i][j] += ma[i - 1][j] + ma[i][j - 1] - ma[i - 1][j - 1];} else printf("error2\n");}}ll diff = 0;ll mindiff = 10000000000000ll;for(i = 1; i <= n; i++) {diff = ma[n][m] - 2 * ma[i][m];if(diff < 0) diff = -diff;mindiff = diff < mindiff ? diff : mindiff;}for(i = 1; i <= m; i++) {diff = ma[n][m] - 2 * ma[n][i];if(diff < 0) diff = -diff;mindiff = diff < mindiff ? diff : mindiff;}printf("%lld\n", mindiff);} else printf("error1\n");return 0;
}