58. 区间和
题目链接 link
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
思路：前缀和
重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。ACM 输入格式。注意：
- 前缀和的写法，第一位是 0
- 按照下面的写法，计算一次就输出一次，会超出限制，可以使用一个数组把结果存起来，然后统一输出
- 按照下面的写法，data 可能会超出限制，报错 下标无法访问，所以需要判断是否有查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
sums = [0]
for i in range(1, n+1):
sums.append(int(data[i]) + sums[-1])
for index in range(n+1, len(data), 2)
a = int(data[index])
b = int(data[index+1])
index += 2
res.append(sums[b+1] - sums[a])
print(res)
|
更改后的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
sums = [0]
for i in range(1, n+1):
sums.append(int(data[i]) + sums[-1])
index = n + 1
res = []
while index < len(data):
a = int(data[index])
b = int(data[index+1])
index += 2
res.append(sums[b+1] - sums[a])
print(res)
|
44. 开发商购买土地
题目链接 link
在一个城市区域内，被划分成了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
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
| import sys
input = sys.stdin.read
data = input().split()
n, m = int(data[0]), int(data[1])
num = [[0] * m for _ in range(n)]
index = 2
for i in range(n):
for j in range(m):
num[i][j] = int(data[index])
index += 1
# 求每一行的和
sumx = [sum(num[i]) for i in range(n)]
# 按行的前缀和
sumx_pre = [sumx[0]]
for i in range(1, n):
sumx_pre.append(sumx[i] + sumx_pre[-1])
minx = float('inf')
# 计算最小的差
for i in range(0, n - 1):
p1 = sumx_pre[i]
p2 = sumx_pre[-1] - sumx_pre[i]
dif = abs(p2 - p1)
if minx > dif:
minx = dif
# 求每一列的和
sumy = [sum(num[i][j] for i in range(n)) for j in range(m)]
# 按列的前缀和
sumy_pre = [sumy[0]]
for j in range(1, m):
sumy_pre.append(sumy[j] + sumy_pre[-1])
miny = float('inf')
for j in range(0, m - 1):
p1 = sumy_pre[j]
p2 = sumy_pre[-1] - sumy_pre[j]
dif = abs(p2 - p1)
if miny > dif:
miny = dif
print(min(miny, minx))
|
优化
在读取数据时，直接求整个矩阵的和。然后分别两个方向求和，模拟行分割和列分割。每求和一行（列），就计算差值。这样可以省去计算前缀和的步骤。
总结
- ACM 格式下，需要自己处理输入，这里重写了 input 方法：
1
2
3
4
| import sys
input = sys.stdin.read
data = input().split()
|
重写的和自带的方法对比如下：
![image]()
重写的方法可以将所有输入作为一整个字符串读取，可以减少 IO 时间。后续使用 .split() 方法来拆分每个输入即可。
