小美的蛋糕切割（美团2024届秋招笔试第一场编程真题）

题目分析：切蛋糕问题切记可以横着切，也可以竖着切。本题目需要快速求得两个矩形的和，可以用二维前缀和数组解决。然后枚举一刀切的位置。

#include <iostream>
#include <algorithm>
using namespace std;
int a[1005][1005];
long long sum[1005][1005];/**< 注意到数据范围可能超过int */
int main()
{
    int i,j,n,m;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            cin>>a[i][j];/**< 二维前缀和数组常见求法 */
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    long long ans=sum[n][m];
    /**< 枚举蛋糕切割，注意可以横着也可以竖着切 */
    for(i=1;i<n;i++)
        ans=min(ans,abs(sum[i][m]-(sum[n][m]-sum[i][m])));/**<sum[i][m]上半块蛋糕  */
    for(j=1;j<m;j++)
        ans=min(ans,abs(sum[n][j]-(sum[n][m]-sum[n][j])));/**<sum[n][j]左半块蛋糕  */
    cout<<ans;
    return 0;
}

解释下：sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];作用