JAVA CCF-202012-2 期末预测之最佳阈值

欢迎访问我的CCF认证解题目录

题目

思路过程

题意很简单，思路也很简单，暴力两层 for 循环，但注意的是，数据量最大达到 $10^5$，显然两层 for 循环会超时。

对于优化来说有很多种方法，我就写我考试时写的方法吧。

预测成功的个数包括两种：

• 小于该安全指数且挂科的人数
• 大于等于该安全指数且没有挂科的人数

我们可以使用 set 升序存储所有的安全指数，对于遍历的安全指数来说，我们可以累计挂科的人数（升序遍历保证），对于没挂科的人数，则是 所有没挂科人数 - 当前遍历到的没挂科人数。

具体看代码实现 ↓

代码

import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // max：预测最多的个数；ans：结果；cnt：以 xx 安全指数预测成功的个数
        int n = in.nextInt(), max = -1, ans = -1, cnt = 0;
        // 存储所有数据，按安全指数升序
        PriorityQueue<int[]> p = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 存储所有的安全指数
        Set<Integer> set = new TreeSet<>();

        // 输入
        while ( n-- != 0 ) {
            int[] temp = new int[]{in.nextInt(), in.nextInt()};
            p.add(temp);
            set.add(temp[0]);
            // 累计没挂科的人数，后面遍历遇到直接--即可。等同于 所有没挂科人数 - 当前遍历到的没挂科人数
            if ( temp[1] == 1 ) cnt++;
        }

        // set 升序遍历
        for ( int next: set ) {
            while ( !p.isEmpty() && p.peek()[0] < next ) {
                // 对于 type==1 来说，预测对的人数 - 1，对于 type==0 来说，预测对的人数 + 1
                if ( p.peek()[1] == 1 ) cnt--;
                else cnt++;
                p.poll();
            }
            if ( cnt >= max ) {
                ans = next;
                max = cnt;
            }
        }
        System.out.println(ans);
    }

}

本文地址：https://blog.csdn.net/weixin_43732798/article/details/111991065