小红书8.28题解

1. 排队(封装‘大臣’对象，加入到优先级队列即可)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 大臣数量
        int n = scanner.nextInt();
        // 重要性方面数量
        int m = scanner.nextInt();
        // 需要帮忙的大臣序号
        int id = scanner.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        TreeSet<Minister> set = new TreeSet<>((m1, m2) -> m1.sum != m2.sum ? m2.sum - m1.sum : m1.id - m2.id);
        for (int i = 0; i < n; i++) {
            Minister minister = new Minister();
            minister.id = i + 1;
            for (int j = 0; j < m; j++) {
                minister.sum += arr[i][j];
            }
            set.add(minister);
        }

        int ans = 1;

        for (Minister minister : set) {
            if (minister.id == id) {
                break;
            } else {
                ans++;
            }
        }
        System.out.println(ans);
    }

    public static class Minister {
        // id序号
        private int id;
        // 分数总和
        private int sum;

        public Minister() {
        }
    }

2. 法术(排序+倒序二分)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 小明会的法术数量
        int n = scanner.nextInt();
        // 最低达到的威力
        long K = scanner.nextLong();
        // 第i种法术对应的威力值
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        long ans = process(K, arr);
        System.out.println(ans);
    }
    
    // 排序，倒序二分最后乘以二
    public static long process(long K, long[] arr) {
        // 题意是只要左右手不使用同一种魔法就行，魔法威力一样的也可以释放。
        Arrays.sort(arr);
        long ans = 0;
        int N = arr.length;
        int L = 0;
        int R = N - 1;
        while (L < R) {
            if (arr[R] * arr[L] >= K) {
                ans += R - L;
                R--;
            } else {
                L++;
            }
        }
        return ans * 2;
    }
}

3. 一对一(从出度最小的点开始构建朋友，找到就标记，然后从出度第二小出发....)

import java.util.*;
public class Main {
    public static class Graph {
        // 点集
        public HashMap<Integer, Node> nodes;

        public Graph() {
            nodes = new HashMap<>();
        }
    }

    public static class Node {
        public int val;
        // 入度
        public int in;
        // 出度
        public int out;
        // 邻居结点
        public ArrayList<Node> nexts;

        public Node(int val) {
            this.val = val;
            in = 0;
            out = 0;
            nexts = new ArrayList<>();
        }
    }

    public static class Edge {
        // 边的开始
        public Node from;
        // 边的结束
        public Node to;

        public Edge(Node from, Node to) {
            this.from = from;
            this.to = to;
        }
    }


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // N个新员工
        int N = scan.nextInt();
        // 构建图
        Graph graph = new Graph();
        for (int i = 0; i < N - 1; i++) {
            int from = scan.nextInt();
            int to = i + 2;
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                // 如果图的点集没有这个点
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            // 构建边
            Edge edge = new Edge(fromNode, toNode);
            // from点的邻居加入to点
            fromNode.nexts.add(toNode);
            // from点的出度+1
            fromNode.out++;
            // to点的入度+1
            toNode.in++;
        }

        // 构建图完成
        HashMap<Integer, Node> nodes = graph.nodes;
        // 从出度最小的点开始找朋友，找了就标记一下。然后从出度第二小的，以此类推。
        // 构建优先级队列，然后加入所有的点Node
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.out - o2.out);
        for (Map.Entry<Integer, Node> entry : nodes.entrySet()) {
            queue.offer(entry.getValue());
        }
        // 去重
        Set<Integer> set = new HashSet<>();
        int ans = 0;
        while (!queue.isEmpty()) {
            // 出度最小的to结点
            Node to = queue.poll();
            // 找到一个from结点，from结点也不能再使用
            Node from = null;
            for (Node x : queue) {
                if (x.nexts.contains(to)) {
                    from = x;
                    break;
                }
            }

            if (!set.contains(to.val) && from != null && !set.contains(from.val)) {
                ans++;
                set.add(to.val);
                set.add(from.val);
            }

        }
        System.out.println(ans);
    }
}