# 44. 开发商购买土地 

> 本题为代码随想录后续扩充题目，还没有视频讲解，顺便让大家练习一下ACM输入输出模式（笔试面试必备）

[题目链接](https://kamacoder.com/problempage.php?pid=1044)

【题目描述】

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 

为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

【输入描述】

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

【输入示例】

3 3
1 2 3
2 1 3
1 2 3

【输出示例】

0

【提示信息】

如果将区域按照如下方式划分：

1 2 | 3
2 1 | 3
1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

【数据范围】：

* 1 <= n, m <= 100；
* n 和 m 不同时为 1。

## 思路 

看到本题，大家如果想暴力求解，应该是 n^3 的时间复杂度， 

一个 for 枚举分割线， 嵌套 两个for 去累加区间里的和。 

如果本题要求 任何两个行（或者列）之间的数值总和，大家在[0058.区间和](./0058.区间和.md) 的基础上 应该知道怎么求。  

就是前缀和的思路，先统计好，前n行的和 q[n]，如果要求矩阵 a行 到 b行 之间的总和，那么就 q[b] - q[a - 1]就好。 

至于为什么是 a - 1，大家去看 [0058.区间和](./0058.区间和.md) 的分析，使用 前缀和 要注意 区间左右边的开闭情况。 

本题也可以使用 前缀和的思路来求解，先将 行方向，和 列方向的和求出来，这样可以方便知道 划分的两个区间的和。 

代码如下：


```CPP 
#include <iostream>
#include <vector>
#include <climits>

using namespace std;
int main () {
    int n, m;
    cin >> n >> m;
    int sum = 0;
    vector<vector<int>> vec(n, vector<int>(m, 0)) ;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> vec[i][j];
            sum += vec[i][j];
        }
    }
    // 统计横向
    vector<int> horizontal(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0 ; j < m; j++) {
            horizontal[i] += vec[i][j];
        }
    }
    // 统计纵向
    vector<int> vertical(m , 0);
    for (int j = 0; j < m; j++) {
        for (int i = 0 ; i < n; i++) {
            vertical[j] += vec[i][j];
        }
    }
    int result = INT_MAX;
    int horizontalCut = 0;
    for (int i = 0 ; i < n; i++) {
        horizontalCut += horizontal[i];
        result = min(result, abs(sum - horizontalCut - horizontalCut));
    }
    int verticalCut = 0;
    for (int j = 0; j < m; j++) {
        verticalCut += vertical[j];
        result = min(result, abs(sum - verticalCut - verticalCut));
    }
    cout << result << endl;
}

```

时间复杂度： O(n^2)

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

时间复杂度也是 O(n^2)

代码如下：

```CPP 
#include <iostream>
#include <vector>
#include <climits>

using namespace std;
int main () {
    int n, m;
    cin >> n >> m;
    int sum = 0;
    vector<vector<int>> vec(n, vector<int>(m, 0)) ;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> vec[i][j];
            sum += vec[i][j];
        }
    }

    int result = INT_MAX;
    int count = 0; // 统计遍历过的行
    for (int i = 0; i < n; i++) {
        for (int j = 0 ; j < m; j++) {
            count += vec[i][j];
            // 遍历到行末尾时候开始统计
            if (j == m - 1) result = min (result, abs(sum - count - count));

        }
    }

    count = 0; // 统计遍历过的列
    for (int j = 0; j < m; j++) {
        for (int i = 0 ; i < n; i++) {
            count += vec[i][j];
            // 遍历到列末尾的时候开始统计
            if (i == n - 1) result = min (result, abs(sum - count - count));
        }
    }
    cout << result << endl;
}
 
```



## 其他语言版本 

### Java

前缀和 

```Java 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int sum = 0;
        int[][] vec = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vec[i][j] = scanner.nextInt();
                sum += vec[i][j];
            }
        }

        // 统计横向
        int[] horizontal = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                horizontal[i] += vec[i][j];
            }
        }

        // 统计纵向
        int[] vertical = new int[m];
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                vertical[j] += vec[i][j];
            }
        }

        int result = Integer.MAX_VALUE;
        int horizontalCut = 0;
        for (int i = 0; i < n; i++) {
            horizontalCut += horizontal[i];
            result = Math.min(result, Math.abs((sum - horizontalCut) - horizontalCut));
            // 更新result。其中，horizontalCut表示前i行的和，sum - horizontalCut表示剩下的和，作差、取绝对值，得到题目需要的“A和B各自的子区域内的土地总价值之差”。下同。
        }

        int verticalCut = 0;
        for (int j = 0; j < m; j++) {
            verticalCut += vertical[j];
            result = Math.min(result, Math.abs((sum - verticalCut) - verticalCut));
        }

        System.out.println(result);
        scanner.close();
    }
}

```

优化暴力 

```Java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int sum = 0;
        int[][] vec = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vec[i][j] = scanner.nextInt();
                sum += vec[i][j];
            }
        }

        int result = Integer.MAX_VALUE;
        int count = 0; // 统计遍历过的行

        // 行切分
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count += vec[i][j];
                // 遍历到行末尾时候开始统计
                if (j == m - 1) {
                    result = Math.min(result, Math.abs(sum - 2 * count));
                }
            }
        }

        count = 0;
        // 列切分
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                count += vec[i][j];
                // 遍历到列末尾时候开始统计
                if (i == n - 1) {
                    result = Math.min(result, Math.abs(sum - 2 * count));
                }
            }
        }

        System.out.println(result);
        scanner.close();
    }
}

```

### python  

前缀和
```python 
def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    sum = 0
    vec = []
    for i in range(n):
        row = []
        for j in range(m):
            num = int(data[idx])
            idx += 1
            row.append(num)
            sum += num
        vec.append(row)

    # 统计横向
    horizontal = [0] * n
    for i in range(n):
        for j in range(m):
            horizontal[i] += vec[i][j]

    # 统计纵向
    vertical = [0] * m
    for j in range(m):
        for i in range(n):
            vertical[j] += vec[i][j]

    result = float('inf')
    horizontalCut = 0
    for i in range(n):
        horizontalCut += horizontal[i]
        result = min(result, abs(sum - 2 * horizontalCut))

    verticalCut = 0
    for j in range(m):
        verticalCut += vertical[j]
        result = min(result, abs(sum - 2 * verticalCut))

    print(result)

if __name__ == "__main__":
    main()


```

优化暴力

```python 
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    sum = 0
    vec = []
    for i in range(n):
        row = []
        for j in range(m):
            num = int(data[idx])
            idx += 1
            row.append(num)
            sum += num
        vec.append(row)

    result = float('inf')
    
    count = 0
    # 行切分
    for i in range(n):
        
        for j in range(m):
            count += vec[i][j]
            # 遍历到行末尾时候开始统计
            if j == m - 1:
                result = min(result, abs(sum - 2 * count))

    count = 0
    # 列切分
    for j in range(m):
        
        for i in range(n):
            count += vec[i][j]
            # 遍历到列末尾时候开始统计
            if i == n - 1:
                result = min(result, abs(sum - 2 * count))

    print(result)

if __name__ == "__main__":
    main()

```

### JavaScript

前缀和
```js
function func() {
    const readline = require('readline')
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    })
    let inputLines = []
    rl.on('line', function (line) {
        inputLines.push(line.trim())
    })

    rl.on('close', function () {
        let [n, m] = inputLines[0].split(" ").map(Number)
        let c = new Array(n).fill(0)
        let r = new Array(m).fill(0)
        let arr = new Array(n)
        let sum = 0//数组总和
        let min = Infinity//设置最小值的初始值为无限大
        //定义数组
        for (let s = 0; s < n; s++) {
            arr[s] = inputLines[s + 1].split(" ").map(Number)
        }
        //每一行的和
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                c[i] += arr[i][j]
                sum += arr[i][j]
            }
        }
        //每一列的和
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                r[j] += arr[i][j]
            }
        }
        let sum1 = 0, sum2 = 0
        //横向切割
        for (let i = 0; i < n; i++) {
            sum1 += c[i]
            min = min < Math.abs(sum - 2 * sum1) ? min : Math.abs(sum - 2 * sum1)
        }
        //纵向切割
        for (let j = 0; j < m; j++) {
            sum2 += r[j]
            min = min < Math.abs(sum - 2 * sum2) ? min : Math.abs(sum - 2 * sum2)
        }
        console.log(min);
    })
}
```

### C

前缀和
```c
#include <stdlib.h>
#include <stdio.h>

int main()
{
    int n = 0, m = 0, ret_ver = 0, ret_hor = 0;

    // 读取行和列的值
    scanf("%d%d", &n, &m);
    // 动态分配数组a(横)和b(纵)的空间
    int *a = (int *)malloc(sizeof(int) * n);
    int *b = (int *)malloc(sizeof(int) * m);

    // 初始化数组a和b
    for (int i = 0; i < n; i++)
    {
        a[i] = 0;
    }
    for (int i = 0; i < m; i++)
    {
        b[i] = 0;
    }

    // 读取区块权值并计算每行和每列的总权值
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int tmp;
            scanf("%d", &tmp);
            a[i] += tmp;
            b[j] += tmp;
        }
    }

    // 计算每列以及每行的前缀和
    for (int i = 1; i < n; i++)
    {
        a[i] += a[i - 1];
    }
    for (int i = 1; i < m; i++)
    {
        b[i] += b[i - 1];
    }

    // 初始化ret_ver和ret_hor为最大可能值
    ret_hor = a[n - 1];
    ret_ver = b[m - 1];

    // 计算按行划分的最小差异
    int ret2 = 0;
    while (ret2 < n)
    {
        ret_hor = (ret_hor > abs(a[n - 1] - 2 * a[ret2])) ? abs(a[n - 1] - 2 * a[ret2]) : ret_hor;
        // 原理同列，但更高级
        ret2++;
    }
    // 计算按列划分的最小差异
    int ret1 = 0;
    while (ret1 < m)
    {
        if (ret_ver > abs(b[m - 1] - 2 * b[ret1]))
        {
            ret_ver = abs(b[m - 1] - 2 * b[ret1]);
        }
        ret1++;
    }

    // 输出最小差异
    printf("%d\n", (ret_ver <= ret_hor) ? ret_ver : ret_hor);

    // 释放分配的内存
    free(a);
    free(b);
    return 0;
}

```

### Go

前缀和

```go
package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
    "math"
)
    
func main() {
    var n, m int
    
    reader := bufio.NewReader(os.Stdin)
    
    line, _ := reader.ReadString('\n')
    line = strings.TrimSpace(line)
    params := strings.Split(line, " ")
    
    n, _ = strconv.Atoi(params[0])
    m, _ = strconv.Atoi(params[1])//n和m读取完成
    
    land := make([][]int, n)//土地矩阵初始化
    
    for i := 0; i < n; i++ {
        line, _ := reader.ReadString('\n')
        line = strings.TrimSpace(line)
        values := strings.Split(line, " ")
        land[i] = make([]int, m)
        for j := 0; j < m; j++ {
            value, _ := strconv.Atoi(values[j])
            land[i][j] = value
        }
    }//所有读取完成
    
    //初始化前缀和矩阵
    preMatrix := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		preMatrix[i] = make([]int, m+1)
	}
    
    for a := 1; a < n+1; a++ {
        for b := 1; b < m+1; b++ {
            preMatrix[a][b] = land[a-1][b-1] + preMatrix[a-1][b] + preMatrix[a][b-1] - preMatrix[a-1][b-1]
        }
    }
    
    totalSum := preMatrix[n][m]
    
    minDiff := math.MaxInt32//初始化极大数，用于比较
    
    //按行分割
    for i := 1; i < n; i++ {
        topSum := preMatrix[i][m]
        
        bottomSum := totalSum - topSum
        
        diff := int(math.Abs(float64(topSum - bottomSum)))
        if diff < minDiff {
            minDiff = diff
        }
    }
    
    //按列分割
    for j := 1; j < m; j++ {
        topSum := preMatrix[n][j]
        
        bottomSum := totalSum - topSum
        
        diff := int(math.Abs(float64(topSum - bottomSum)))
        if diff < minDiff {
            minDiff = diff
        }
    }    
    
    fmt.Println(minDiff) 
}
```