\44. 开发商购买土地（第五期模拟笔试）
题目描述
在一个城市区域内，被划分成了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。
//前缀和
#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];//把第 i 行加进来，代表切到第 i 行下面。// 上面总和是 cut,下面总和是 sum - cut,差值 = cut - (sum - cut) = sum - 2*cutresult = 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;
}
-
看到本题，大家如果想暴力求解，应该是 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];}}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;
}
-
其实本题可以在暴力求解的基础上，优化一下，就不用前缀和了，在行向遍历的时候，遇到行末尾就统一一下， 在列向遍历的时候，遇到列末尾就统计一下。
时间复杂度也是 O(n^2)
普通暴力思想，练习代码模拟水平
#include <iostream>
#include <vector>
#include <climits> // 用于 INT_MAX
#include <cmath> // 用于 abs() 绝对值
using namespace std;int main() {// 一、输入部分：读入矩阵的行数 n 和列数 mint n, m;cin >> n >> m;// 定义 n 行 m 列的二维数组（矩阵），存储土地价值vector<vector<int>> a(n, vector<int>(m));// 读入矩阵的每个数字for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[i][j];}}// 定义答案：最小差值// 先初始化为“无穷大”，后面不断更新成更小的int min_diff = INT_MAX;// ======================================================// 二、暴力枚举：所有【横着切一刀】的可能性// 思路：切在某一行下面，把矩阵分成 上半部分 + 下半部分// ======================================================// 循环：尝试每一个横向切割位置// cut 表示：切在第 cut 行的下面// 注意：不能切最后一行下面，否则下半部分为空，所以是 cut < n-1for (int cut = 0; cut < n - 1; cut++) {// 用来存储：切完后，【上半部分所有土地的总价值】int top_sum = 0;// 暴力累加：从上到下，把 0 ~ cut 行所有数字加起来for (int i = 0; i <= cut; i++) {for (int j = 0; j < m; j++) {top_sum += a[i][j];}}// 暴力计算：整个矩阵的总价值int total = 0;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)total += a[i][j];// 计算当前切法的差值：// 上半部分和 - 下半部分和 的绝对值// 下半部分和 = 总和 - 上半部分和int diff = abs(top_sum - (total - top_sum));// 更新最小差值：保留最小的那个min_diff = min(min_diff, diff);}// ======================================================// 三、暴力枚举：所有【竖着切一刀】的可能性// 思路：切在某一列右边，把矩阵分成 左半部分 + 右半部分// ======================================================// 循环：尝试每一个纵向切割位置// cut 表示：切在第 cut 列的右边// 同样不能切最后一列，所以 cut < m-1for (int cut = 0; cut < m - 1; cut++) {// 用来存储：切完后，【左半部分所有土地的总价值】int left_sum = 0;// 暴力累加：从左到右，把 0 ~ cut 列所有数字加起来for (int j = 0; j <= cut; j++) {for (int i = 0; i < n; i++) {left_sum += a[i][j];}}// 再次计算整个矩阵总和（暴力写法，不优化）int total = 0;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)total += a[i][j];// 计算当前切法的差值int diff = abs(left_sum - (total - left_sum));// 更新最小差值min_diff = min(min_diff, diff);}// 输出所有切法中，最小的差值cout << min_diff << endl;return 0;
}