开发商购买土地
题目描述
在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。
现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分。
输入描述
第一行输入两个正整数，代表 n 和 m。
接下来的 n 行，每行输出 m 个正整数。
输出描述
输出一个整数，代表 A 公司和 B 公司各自的子区域内的土地总价值之差的最小值。
输入示例
3 3
1 2 3
2 1 3
1 2 3
输出示例
0
提示信息
如果将区域按照如下方式划分：
1 2 | 3
2 1 | 3
1 2 | 3
两个子区域内土地总价值之间的最小差距可以达到 0。
思路
以行为例，可以将每一行的前缀和求出来，然后遍历每一行，将每一行的前缀和分为两部分，一部分为前i个元素的和，另一部分为后n-i个元素的和，然后取两者的差的绝对值，取最小值即可。
前缀和可以将复杂度从$O(n^3)$降到$O(n^2)$。
代码
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
| #include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n{},m{};
cin >> n>>m;
vector<vector<int>>s(n,vector<int>(m));
int sum = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> s[i][j];
sum += s[i][j];
}
}
vector<int> row(n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
row[i] += s[i][j];
}
}
vector<int> col(m);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
col[i] += s[j][i];
}
}
int res = INT32_MAX;
int sub_row = 0;
for(int i = 0;i<n;i++){
sub_row += row[i];
res = min(res,abs(sum-2*sub_row));
}
int sub_col = 0;
for(int i =0; i<m;i++){
sub_col += col[i];
res = min(res,abs(sum-2*sub_col));
}
cout << res << endl;
return 0;
}
|
Ref
programmercarl