616 lines
14 KiB
Markdown
616 lines
14 KiB
Markdown
|
||
# 44. 开发商购买土地
|
||
|
||
> 本题为代码随想录后续扩充题目，还没有视频讲解，顺便让大家练习一下ACM输入输出模式（笔试面试必备）
|
||
|
||
[题目链接](https://kamacoder.com/problempage.php?pid=1044)
|
||
|
||
【题目描述】
|
||
|
||
在一个城市区域内，被划分成了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.区间和](./0058.区间和.md) 的基础上 应该知道怎么求。
|
||
|
||
就是前缀和的思路，先统计好，前n行的和 q[n]，如果要求矩阵 a行 到 b行 之间的总和，那么就 q[b] - q[a - 1]就好。
|
||
|
||
至于为什么是 a - 1，大家去看 [0058.区间和](./0058.区间和.md) 的分析，使用 前缀和 要注意 区间左右边的开闭情况。
|
||
|
||
本题也可以使用 前缀和的思路来求解，先将 行方向，和 列方向的和求出来，这样可以方便知道 划分的两个区间的和。
|
||
|
||
代码如下：
|
||
|
||
|
||
```CPP
|
||
#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;
|
||
}
|
||
|
||
```
|
||
|
||
时间复杂度： O(n^2)
|
||
|
||
其实本题可以在暴力求解的基础上，优化一下，就不用前缀和了，在行向遍历的时候，遇到行末尾就统一一下， 在列向遍历的时候，遇到列末尾就统计一下。
|
||
|
||
时间复杂度也是 O(n^2)
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
#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;
|
||
}
|
||
|
||
```
|
||
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### Java
|
||
|
||
前缀和
|
||
|
||
```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 - horizontalCut) - horizontalCut));
|
||
// 更新result。其中，horizontalCut表示前i行的和，sum - horizontalCut表示剩下的和，作差、取绝对值，得到题目需要的“A和B各自的子区域内的土地总价值之差”。下同。
|
||
}
|
||
|
||
int verticalCut = 0;
|
||
for (int j = 0; j < m; j++) {
|
||
verticalCut += vertical[j];
|
||
result = Math.min(result, Math.abs((sum - verticalCut) - verticalCut));
|
||
}
|
||
|
||
System.out.println(result);
|
||
scanner.close();
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
优化暴力
|
||
|
||
```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 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();
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
### python
|
||
|
||
前缀和
|
||
```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()
|
||
|
||
|
||
```
|
||
|
||
优化暴力
|
||
|
||
```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)
|
||
|
||
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()
|
||
|
||
```
|
||
|
||
### JavaScript
|
||
|
||
前缀和
|
||
```js
|
||
function func() {
|
||
const readline = require('readline')
|
||
const rl = readline.createInterface({
|
||
input: process.stdin,
|
||
output: process.stdout
|
||
})
|
||
let inputLines = []
|
||
rl.on('line', function (line) {
|
||
inputLines.push(line.trim())
|
||
})
|
||
|
||
rl.on('close', function () {
|
||
let [n, m] = inputLines[0].split(" ").map(Number)
|
||
let c = new Array(n).fill(0)
|
||
let r = new Array(m).fill(0)
|
||
let arr = new Array(n)
|
||
let sum = 0//数组总和
|
||
let min = Infinity//设置最小值的初始值为无限大
|
||
//定义数组
|
||
for (let s = 0; s < n; s++) {
|
||
arr[s] = inputLines[s + 1].split(" ").map(Number)
|
||
}
|
||
//每一行的和
|
||
for (let i = 0; i < n; i++) {
|
||
for (let j = 0; j < m; j++) {
|
||
c[i] += arr[i][j]
|
||
sum += arr[i][j]
|
||
}
|
||
}
|
||
//每一列的和
|
||
for (let i = 0; i < n; i++) {
|
||
for (let j = 0; j < m; j++) {
|
||
r[j] += arr[i][j]
|
||
}
|
||
}
|
||
let sum1 = 0, sum2 = 0
|
||
//横向切割
|
||
for (let i = 0; i < n; i++) {
|
||
sum1 += c[i]
|
||
min = min < Math.abs(sum - 2 * sum1) ? min : Math.abs(sum - 2 * sum1)
|
||
}
|
||
//纵向切割
|
||
for (let j = 0; j < m; j++) {
|
||
sum2 += r[j]
|
||
min = min < Math.abs(sum - 2 * sum2) ? min : Math.abs(sum - 2 * sum2)
|
||
}
|
||
console.log(min);
|
||
})
|
||
}
|
||
```
|
||
|
||
### C
|
||
|
||
前缀和
|
||
```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;
|
||
}
|
||
|
||
```
|
||
|
||
### Go
|
||
|
||
前缀和
|
||
|
||
```go
|
||
package main
|
||
|
||
import (
|
||
"fmt"
|
||
"os"
|
||
"bufio"
|
||
"strings"
|
||
"strconv"
|
||
"math"
|
||
)
|
||
|
||
func main() {
|
||
var n, m int
|
||
|
||
reader := bufio.NewReader(os.Stdin)
|
||
|
||
line, _ := reader.ReadString('\n')
|
||
line = strings.TrimSpace(line)
|
||
params := strings.Split(line, " ")
|
||
|
||
n, _ = strconv.Atoi(params[0])
|
||
m, _ = strconv.Atoi(params[1])//n和m读取完成
|
||
|
||
land := make([][]int, n)//土地矩阵初始化
|
||
|
||
for i := 0; i < n; i++ {
|
||
line, _ := reader.ReadString('\n')
|
||
line = strings.TrimSpace(line)
|
||
values := strings.Split(line, " ")
|
||
land[i] = make([]int, m)
|
||
for j := 0; j < m; j++ {
|
||
value, _ := strconv.Atoi(values[j])
|
||
land[i][j] = value
|
||
}
|
||
}//所有读取完成
|
||
|
||
//初始化前缀和矩阵
|
||
preMatrix := make([][]int, n+1)
|
||
for i := 0; i <= n; i++ {
|
||
preMatrix[i] = make([]int, m+1)
|
||
}
|
||
|
||
for a := 1; a < n+1; a++ {
|
||
for b := 1; b < m+1; b++ {
|
||
preMatrix[a][b] = land[a-1][b-1] + preMatrix[a-1][b] + preMatrix[a][b-1] - preMatrix[a-1][b-1]
|
||
}
|
||
}
|
||
|
||
totalSum := preMatrix[n][m]
|
||
|
||
minDiff := math.MaxInt32//初始化极大数，用于比较
|
||
|
||
//按行分割
|
||
for i := 1; i < n; i++ {
|
||
topSum := preMatrix[i][m]
|
||
|
||
bottomSum := totalSum - topSum
|
||
|
||
diff := int(math.Abs(float64(topSum - bottomSum)))
|
||
if diff < minDiff {
|
||
minDiff = diff
|
||
}
|
||
}
|
||
|
||
//按列分割
|
||
for j := 1; j < m; j++ {
|
||
topSum := preMatrix[n][j]
|
||
|
||
bottomSum := totalSum - topSum
|
||
|
||
diff := int(math.Abs(float64(topSum - bottomSum)))
|
||
if diff < minDiff {
|
||
minDiff = diff
|
||
}
|
||
}
|
||
|
||
fmt.Println(minDiff)
|
||
}
|
||
```
|
||
|