#区间和

开发商购买土地

题目描述

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。

为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

【输入描述】

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

数据范围：

1 <= n, m <= 100；
n 和 m 不同时为 1。

思路

1. 输入矩阵的同时计算最大值，同时给出每一列的区间和：[0,i]
2. 遍历数组得到每一行的区间和
3. 分别按行、列遍历得到差值最小的res，然后输出结果。

==Note==

• 第三步按行列进行遍历得到最小差值，应该是可以优化的。比如刚好遍历到总数的一半时，就不需要再进行计算了。
• 同时在遍历到大于total的一半的时候，之前的区间和[0,i-1]应该是按行（列）计算的最优，但是如果要回溯到原来的状态又可能需要进一步判断，代码的判断就更加冗余了。

具体代码

Java

class Main{  
    public static void main(String[] a){  
        Scanner scanner = new Scanner(System.in);  
        int row = 1;  
        int column = 1;  
        row = scanner.nextInt();  
        column = scanner.nextInt();  
        int total = 0;  
        int[][] field = new int[row][column];  
        int[] rowRecord = new int[row + 1];  
        int[] columnRecord = new int[column + 1];  
        int res = Integer.MAX_VALUE;  

        // 填充行;  
        for(int i = 0; i < row; i++){  
            int rowTotal = 0;  
            for(int j = 0; j < column; j++){  
                field[i][j] = scanner.nextInt();  
                rowTotal += field[i][j];  
            }  
            rowRecord[i + 1] =rowRecord[i] + rowTotal;  
            total += rowTotal;  
        }  

        // 填充列;  
        for(int j = 0; j < column; j++){  
            int columnTotal = 0;  
            for(int i = 0; i < row; i++){  
                columnTotal += field[i][j];  
            }  
            columnRecord[j + 1] = columnRecord[j] + columnTotal;  

        }  

        // 判断行  
        for(int i = 1; i <= row; i++){  
            res = Math.min(rowRecord[i] * 2 - total, res);  
        }  

        // 判断列  
        for(int j = 1; j <= column; j++){  
           res = Math.min(columnRecord[j] * 2 -total,res);  
        }  
        System.out.println(res);  
    }  
}