0044.开发商购买土地.md

44. 开发商购买土地

题目链接

C++

Java

/**
 * 思路：计算出二维数组的二维前缀和，然后分别按行遍历和按列遍历，计算出最小值
*/
import java.util.Scanner;

public class twoDPrefixSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        long[][] landValues = new long[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                landValues[i][j] = scanner.nextInt();
            }
        }
        // 当二维矩阵的大小为 1 时，只有一个开发商能拿到这块土地
        if (n == 1 && m == 1) {
            System.out.println(landValues[0][0]);
        } else {
            System.out.println(findMinAverageDifference(landValues));
        }
        scanner.close();
    }
    public static long findMinAverageDifference(long[][] landValues) {
        int n = landValues.length;
        int m = landValues[0].length;
        long[][] prefixSumArray = new long[n][m];  // 二维前缀和数组
        long result = Integer.MAX_VALUE;  // 绝对值之差
        
        prefixSumArray[0][0] = landValues[0][0]; // 初始化
    
        // 处理第一行
        for (int j = 1; j < m; j++) {
            prefixSumArray[0][j] = landValues[0][j] + prefixSumArray[0][j - 1];
        }
    
        // 处理第一列
        for (int i = 1; i < n; i++) {
            prefixSumArray[i][0] = landValues[i][0] + prefixSumArray[i - 1][0];
        }
    
        // 计算剩余的前缀和数组
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                prefixSumArray[i][j] = landValues[i][j] + prefixSumArray[i - 1][j] + prefixSumArray[i][j - 1] - prefixSumArray[i - 1][j - 1];
            }
        }
    
        // 计算结果时，确保不会越界
        for (int i = 0; i < n; i++) {
            result = Math.min(result, Math.abs(prefixSumArray[i][m - 1] - (prefixSumArray[n - 1][m - 1] - prefixSumArray[i][m - 1])));
        }
    
        for (int j = 0; j < m; j++) {
            result = Math.min(result, Math.abs(prefixSumArray[n - 1][j] - (prefixSumArray[n - 1][m - 1] - prefixSumArray[n - 1][j])));
        }
        return result;
    }
}

Python

# 区域和最平均
# 统计横竖方向上的和，然后遍历求左右差最小
def get_min(nums):
    res = float('inf')
    left = 0
    right = sum(nums)
    for i in nums:
        left += i
        right -= i
        res = min(res, abs(left-right))
    return res

m, n = map(int, input().split(" "))
input_matrix = []

for i in range(m):
    row = input().strip().split()  # 分割每一行的元素
    row = [int(x) for x in row]  # 将元素转换为整数
    input_matrix.append(row)  # 将每一行添加到矩阵中
# 计算每行的和
row_sums = [sum(row) for row in input_matrix]

# 计算每列的和
col_sums = [sum(col) for col in zip(*input_matrix)]

print(min(get_min(row_sums), get_min(col_sums)))

Go

JS

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n=0, m=0;
let datas=new Array();
rl.on('line', function(line) {
    if(n === 0) {
        let tokens = line.split(' ').map(item => parseInt(item));
        n = tokens[0];
        m = tokens[1];
    }else{
        let tokens = line.split(' ').map(item => parseInt(item));
        datas.push(tokens);
        if(datas.length === n) {
            const record = new Array(n+1).fill(0).map(item => new Array(m+1).fill(0));
            for(let i=1; i<=n; i++) { // 计算前缀和
                for(let j=1; j<=m; j++) {
                    record[i][j] = record[i-1][j] + record[i][j-1] - record[i-1][j-1] + datas[i-1][j-1]; // 计算前缀和公式，注意下标
                }
            }
            let result = Number.MAX_VALUE;
            // 按横划分，上面的区域属于公司A，下面的区域属于公司B
            for(let i=2; i<=n; i++) { // 由于record下标从1开始算的
                let temp = record[n][m] - record[i-1][m]; // 计算得到公司B的土地总价值
                result = Math.min(Math.abs(record[i-1][m] - temp), result);
            }
            // 按列划分，左边的区域属于公司A，右边的区域属于公司B
            for(let j=2; j<=m; j++) { // 由于record下标从1开始算的
                let temp = record[n][m] - record[n][j-1]; // 计算得到公司B的土地总价值
                result = Math.min(Math.abs(record[n][j-1] - temp), result);
            }
            console.log(result)
        }
    }
});

C