# 44. 开发商购买土地
本题为代码随想录后续扩充题目，还没有视频讲解，顺便让大家练习一下ACM输入输出模式（笔试面试必备）
【题目描述】
在一个城市区域内，被划分成了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.区间和 的基础上 应该知道怎么求。
就是前缀和的思路，先统计好，前n行的和 q[n]，如果要求矩阵 a行 到 b行 之间的总和，那么就 q[b] - q[a - 1]就好。
至于为什么是 a - 1，大家去看 0058.区间和 的分析，使用 前缀和 要注意 区间左右边的开闭情况。
本题也可以使用 前缀和的思路来求解，先将 行方向，和 列方向的和求出来，这样可以方便知道 划分的两个区间的和。
代码如下：
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
时间复杂度： O(n^2)
其实本题可以在暴力求解的基础上，优化一下，就不用前缀和了，在行向遍历的时候，遇到行末尾就统一一下， 在列向遍历的时候，遇到列末尾就统计一下。
时间复杂度也是 O(n^2)
代码如下：
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 其他语言版本
# 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 - 2 * horizontalCut));
}
int verticalCut = 0;
for (int j = 0; j < m; j++) {
verticalCut += vertical[j];
result = Math.min(result, Math.abs(sum - 2 * verticalCut));
}
System.out.println(result);
scanner.close();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
优化暴力
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();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
优化暴力
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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
@2021-2024 代码随想录 版权所有 粤ICP备19156078号