应用题-数组专题-等价切分( 前缀和 )
- 版权声明：本站原创文章，于2026-04-20，由 管理员 发表。
- 转载请注明： 应用题-数组专题-等价切分( 前缀和 ) | CodeGarden
给定一个 n x m 的整数矩阵，将其用一条水平线或垂直线切成两个非空连通子矩阵，使得两个子矩阵的元素和的差值最小，输出该最小差值。
输入描述
第一行输入两个正整数，代表 n 和 m。
接下来的 n 行，每行输出 m 个正整数。
```
输入示例
3 3
1 2 3
2 1 3
1 2 3
```
数据范围：
1 <= n, m <= 100；
n 和 m 不同时为 1。
```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
# 统计行的前缀和
# 统计列的前缀和
# 统计矩阵数值总和
prf_row = [ 0 for _ in range( n ) ]
prf_col = [ 0 for _ in range( m ) ]
matrix_sum = 0
for i in range( n ):
for j in range( m ):
val = int( data[ idx ] )
idx += 1
prf_row[ i ] += val
prf_col[ j ] += val
matrix_sum += val
# 枚举分割线
ans = float( 'inf' )
horizontal = 0
for i in range( n - 1 ):
horizontal += prf_row[ i ]
ans = min( ans, abs( matrix_sum - horizontal - horizontal ) )
vertical = 0
for j in range( m - 1 ):
vertical += prf_col[ j ]
ans = min( ans, abs( matrix_sum - vertical - vertical ) )
print( ans )
if __name__ == "__main__":
main()
```