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

C