解题思路

看到题目后，我们很容易得出一个结论：令所有蛋糕的美味度总和为sum。那么当s1越接近sum的一半，|s1 - s2|就越小。

同时s1 + s2 = sum，故|s1 - s2| = |sum - s1 - s1|。

本题的关键是求计算s1，即枚举所有正方形的美味度。

将一维数组的前缀和扩展到二维

对于一维数组a，我们可以维护一个前缀和数组s。s[i]表示a[0]到a[i]的和。那么当我们要求数组a的一段连续子数组的和，比如a[i]到a[j]的和，就可以得到答案 = s[j] - s[i - 1]。

类似的，将一维数组扩展到二维数组。

s[i][j]表示从a[0][0]开始，a[i][j]结束的矩形范围的所有值之和【面积】。

那么我们求二维数组内的任意一块矩形的【面积】，比如从a[x1][y1]，到a[x2][y2]。可以得到答案 =

s[x2][y2] - s[x1- 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

上面这个式子可以看成一个大矩形的面积 - 左侧部分矩形面积 - 上侧部分矩形面积 + 左侧和上侧两个矩形重合部分面积

如下图红框矩形面积 = 大黑框面积 - 绿框面积 - 蓝框面积 + 蓝绿框重合面积。

贪心

遍历二维数组的每个位置，以该位置作为正方形的右下角顶点，可以得到边长为 l 的正方形面积

s1 = s[i][j] - s[i][j - l] - s[i - l][j] + s[i - l][j - l];

很显然边长 l 是一个可以变化的值，如果用一个for循环从大到小遍历一遍，那么就可以得到多个s1，从大到小变化。

根据贪心的思路，s1越接近总面积sum的一半越好。因此当s1小于sum / 2时，就不用计算边长更小的正方形了，因为那肯定不会是更优的解。

C++代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int m, n;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
    vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0)); //前缀和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            s[i][j] = s[i][j - 1] + a[i][j]; //当前行的前缀和
        }
        for (int j = 1; j <= m; ++j) {
            s[i][j] += s[i - 1][j]; //扩展到面积
        }
    }
    long long sum = s[n][m]; //总面积
    long long half = sum / 2; //总面积的一半
    long long ans = sum;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int l = min(i, j); l >= 1; --l) { //l表示正方形边长
                long long s1 = s[i][j] - s[i][j - l] - s[i - l][j] + s[i - l][j - l];
                ans = min(ans, abs(sum - s1 - s1)); //更新结果
                if (s1 <= half) break; //继续循环不可能得到更优结果
            }
        }
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")