【CSP：202012-2】期末预测之最佳阈值（Java）

本文主要是介绍【CSP：202012-2】期末预测之最佳阈值（Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

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

题目描述

求解思路

前缀和

根据题意我们可以得知： $θ$ 值为 a[i].y 时的预测正确的次数等于 a[i].y 前面有多少个 result = 0 以及后面有多少个result = 1。
定义Score类用来存储y和result，其中sum0表示a[1]到a[i]有多少个result = 0，sum1表示a[1]到a[i]有多少个result = 1，sum表示阈值取到a[i].y时预测正确的次数。然后写一个类的比较方法用于排序。
数组a[]用来存放每个同学的y和result。
对数组进行排序，并求得sum0和sum1。
遍历数组，如果相邻的两个学生的安全指数相同，则不用处理直接得出sum值；否则利用前缀和计算出当前的sum，然后和max进行比较，相同的话取大的那个。

实现代码

import java.util.Arrays;
import java.util.Scanner;class Score {int y;int result;int sum0; // 记录a[1]——a[i] 有多少result = 0int sum1; // 记录a[1]——a[i] 有多少result = 1int sum; //a[i].y时的预测正确次数public int compare(Score score) {if (this.y > score.y) {return 1;} else if (this.y < score.y) {return -1;} else {return Integer.compare(this.result, score.result);}}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int m = in.nextInt();Score[] a = new Score[m + 1];a[0] = new Score();for (int i = 1; i <= m; i++) {a[i] = new Score();a[i].y = in.nextInt();a[i].result = in.nextInt();}Arrays.sort(a, Score::compare);for (int i = 1; i <= m; i++) {if (a[i].result == 1) {a[i].sum0 = a[i - 1].sum0;a[i].sum1 = a[i - 1].sum1 + 1;} else {a[i].sum0 = a[i - 1].sum0 + 1;a[i].sum1 = a[i - 1].sum1;}}int ans = 0;int max = 0;for (int i = 1; i <= m; i++) {if (a[i].y == a[i - 1].y) {a[i].sum = a[i - 1].sum;} else {a[i].sum = a[i - 1].sum0 + a[m].sum1 - a[i - 1].sum1;}if (max <= a[i].sum) {max = a[i].sum;ans = a[i].y;}}System.out.println(ans);}
}