44. 开发商购买土地

题目

自己写的：

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
int n, m;
int q[N][N], s[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ ) cin >> q[i][j];
        
    s[0][0] = q[0][0];
    for (int i = 1; i < n; i ++ ) s[i][0] = s[i - 1][0] + q[i][0];
    for (int j = 1; j < m; j ++ ) s[0][j] = s[0][j - 1] + q[0][j];
    
    for (int i = 1; i < n; i ++ )
        for (int j = 1; j < m; j ++ ) 
            s[i][j] = s[i - 1][j] + s[i][j - 1] + q[i][j] - s[i - 1][j - 1];
    
    int result = INT32_MAX;
    for (int i = 0; i < n - 1; i ++ )
    {
        result = min(result, abs(s[n - 1][m - 1] - 2 * s[i][m - 1]));
    }
    
    for (int j = 0; j < m - 1; j ++ )
    {
        result = min(result, abs(s[n - 1][m - 1] - 2 * s[n - 1][j]));
    }
    
    cout << result << endl;
    
    return 0;
    
}

这个是一个二维前缀和的题目。

然后这题给我的一个惨痛的教训就是：

在写for循环的时候，注意不要把维数搞混了，这题的两维的维数是不同的，行是n，列是m，不要一股脑全写n，特别是针对这种二维维数不同的题目。

补充：

看了下卡哥的题解，卡哥给了两种方案，一种用前缀和（不过是一维前缀和，并不是二维前缀和），一种是在暴力求解的基础上优化一下。

第一种解法：

先将行方向，和列方向的和求出来，这样可以方便知道划分的两个区间的和。

第二种解法：

在暴力求解的基础上，优化一下，就不用前缀和了，在行向遍历的时候，遇到行末尾就统一一下， 在列向遍历的时候，遇到列末尾就统计一下。

附上卡哥题解链接 44. 开发商购买土地