矩形分割（洛谷P1324题题解，Java语言描述）

╰+哭是因爲堅強的太久メ 2022-10-22 04:25 138阅读 0赞

# 题目要求 #

[题目链接][Link 1]

![在这里插入图片描述][20210404001812339.png]

# 分析 #

用贪心做。

理由是：从行或列中优先选择一个当前最大的，让最大的值乘以最小的权，可以得到最小值，即最优解。

贪心需要排序，为啥选择`Integer[]`而不是`int[]`呢？因为不然`Comparator.reverseOrder()`会没法用。

# AC代码 #

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
    
    public class Main {
        
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt()-1, m = sc.nextInt()-1;
            long result = 0;
            // 必须用这个
            Integer[] row = new Integer[n], line = new Integer[m];
            for (int i = 0; i < n; i++) {
        
                row[i] = sc.nextInt();
            }
            for (int j = 0; j < m; j++) {
        
                line[j] = sc.nextInt();
            }
            // 升序改降序
            Arrays.sort(row, Comparator.reverseOrder());
            Arrays.sort(line, Comparator.reverseOrder());
            long i_count = 1, j_count = 1;
            for (int i = 0, j = 0; i < n || j < m; ) {
        
                if (i == n) {
        
                    result += i_count*line[j];
                    j_count++;
                    j++;
                } else if (j == m || row[i] > line[j]) {
        
                    result += j_count*row[i];
                    i_count++;
                    i++;
                } else {
        
                    result += i_count*line[j];
                    j_count++;
                    j++;
                }
            }
            System.out.println(result);
            sc.close();
        }
    
    }

[Link 1]: https://www.luogu.com.cn/problem/P1324
[20210404001812339.png]: /images/20221022/b9524cb96f9f468297610d490817659b.png