题解 | 排座椅-Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 行数
        int m = sc.nextInt(); // 列数
        int k = sc.nextInt(); // 横向通道数量
        int l = sc.nextInt(); // 纵向通道数量
        int d = sc.nextInt(); // 交头接耳的对数

        // 统计每个横向通道能隔开的对数
        int[] horizontal = new int[n];
        // 统计每个纵向通道能隔开的对数
        int[] vertical = new int[m];

        for (int i = 0; i < d; i++) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            if (x1 == x2) {
                // 左右相邻，属于纵向通道
                int col = Math.min(y1, y2);
                vertical[col]++;
            } else {
                // 上下相邻，属于横向通道
                int row = Math.min(x1, x2);
                horizontal[row]++;
            }
        }

        // 选择最优的横向通道
        List<Integer> hList = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            hList.add(i);
        }
        // 按重要性降序排序，重要性相同则按位置升序
        Collections.sort(hList, (a, b) -> {
            if (horizontal[a] != horizontal[b]) {
                return Integer.compare(horizontal[b], horizontal[a]);
            } else {
                return Integer.compare(a, b);
            }
        });
        // 取前k个并排序
        List<Integer> hResult = hList.subList(0, k);
        Collections.sort(hResult);

        // 选择最优的纵向通道
        List<Integer> vList = new ArrayList<>();
        for (int i = 1; i < m; i++) {
            vList.add(i);
        }
        // 按重要性降序排序，重要性相同则按位置升序
        Collections.sort(vList, (a, b) -> {
            if (vertical[a] != vertical[b]) {
                return Integer.compare(vertical[b], vertical[a]);
            } else {
                return Integer.compare(a, b);
            }
        });
        // 取前l个并排序
        List<Integer> vResult = vList.subList(0, l);
        Collections.sort(vResult);

        // 输出横向通道
        for (int i = 0; i < hResult.size(); i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(hResult.get(i));
        }
        System.out.println();

        // 输出纵向通道
        for (int i = 0; i < vResult.size(); i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(vResult.get(i));
        }
        System.out.println();
    }
}