JAVA CCF-202012-2 期末预测之最佳阈值
程序员文章站
2022-06-19 11:40:12
欢迎访问我的CCF认证解题目录题目思路过程题意很简单,思路也很简单,暴力两层 for 循环,但注意的是,数据量最大达到 10510^5105,显然两层 for 循环会超时。对于优化来说有很多种方法,我就写我考试时写的方法吧。预测成功的个数包括两种:小于该安全指数且挂科的人数大于等于该安全指数且没有挂科的人数我们可以使用 set 升序存储所有的安全指数,对于遍历的安全指数来说,我们可以累计挂科的人数(升序遍历保证),对于没挂科的人数,则是 所有没挂科人数 - 当前遍历到的没挂科人数。...
欢迎访问我的CCF认证解题目录
题目
思路过程
题意很简单,思路也很简单,暴力两层 for 循环,但注意的是,数据量最大达到 1 0 5 10^5 105,显然两层 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
上一篇: ArrayList的数据删除及排序
下一篇: 为了搞清楚类加载,竟然手撸JVM!