题解 | 排座椅

import java.util.*;
import java.util.stream.Collectors;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

/*
    思路：
        先找出横向、纵向的“交头接耳”对的数量
        再找出前k个横向最多“交头接耳”对的数量，以及前l个纵向
        完成

    注意：
        2≦n,m≦10^3，0<k<n; 0<l<m; 0<d≦2×min{n×m,2×10^3}
 */

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        Map<Integer, Integer> kmap = new HashMap<>();  // 下标 -> 每行“交头接耳”对数量数量
        Map<Integer, Integer> lmap = new HashMap<>();  // 下标 -> 每列“交头接耳”对数量数量

        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt(), m = in.nextInt(), k = in.nextInt(), l = in.nextInt(), d = in.nextInt();
            int x, y, p, q;
            for (int i = 0; i < d; i++) {
                x = in.nextInt(); y = in.nextInt(); p = in.nextInt(); q = in.nextInt();
                int min_pos;
                if(x == p){ // 同一行，为纵向“交头接耳”对
                    min_pos = Math.min(y, q);
                    if(lmap.containsKey(min_pos)){
                        lmap.replace(min_pos, lmap.get(min_pos)+1);
                    }
                    else{
                        lmap.put(min_pos, 1);
                    }
                }
                else if(y == q){ // 同一列，为横向“交头接耳”对
                    min_pos = Math.min(x, p);
                    if(kmap.containsKey(min_pos)){
                        kmap.replace(min_pos, kmap.get(min_pos)+1);
                    }
                    else{
                        kmap.put(min_pos, 1);
                    }
                }
            }
            // 先对“交头接耳”对数量排序，再对下标排序
            List<Map.Entry<Integer, Integer>> klist = kmap.entrySet().stream().sorted((o1, o2)->
                    o2.getValue() - o1.getValue()
            ).limit(k).sorted((o1, o2)->
                    o1.getKey() - o2.getKey()).collect(Collectors.toList());

            List<Map.Entry<Integer, Integer>> llist = lmap.entrySet().stream().sorted((o1, o2)->
                    o2.getValue() - o1.getValue()
            ).limit(l).sorted((o1, o2)->
                    o1.getKey() - o2.getKey()).collect(Collectors.toList());

            // 输出
            for (Map.Entry<Integer, Integer> Entry : klist) {
                System.out.print(Entry.getKey() + " ");
            }
            System.out.println();
            for (Map.Entry<Integer, Integer> Entry : llist) {
                System.out.print(Entry.getKey() + " ");
            }
            

        }
    }

}