CSP202012_2期末预测之最佳阈值Java实现

题干

见官网

注意点

时间限制：1s

解题思路

1、暴力嵌套循环 O(n^2) 70分

2、排序+前缀和

首先我们要知道评价一个阈值好坏的标注：预测正确的数目越大越好 对于一个阈值来说： 预测正确数目 = 阈值小于自己且挂科 + 阈值大于等于自己且未挂科

既然循环不可以，就用前缀和 O(m+n) 处理一下数据（这或许也是空间换时间？ 1、新建数组sum[ Num +1 ]，其中Num 是输入的行数 2、对于sum[ i ]，意思是第 i 个数及之前未挂科人数的和

代码：

		int[] sum=new int[Num+1];
        sum[0]=0;
        for(int i=1;i<=Num;i++){
            sum[i]=sum[i-1]+pairs[i-1].getY();
//            System.out.println(sum[i]);
        }

对于两个数组：pairs从0开始，sum从1开始，见下图表格：

pairs计数	pairs	sum	sum计数
0	0 0	0	1
1	1 0	0	2
2	1 1	1	3
3	3 1	2	4
4	5 1	3	5
5	7 1	4	6

代码

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class CCF202012_2 {
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int Num=scanner.nextInt();
        Pair[] pairs=new Pair[Num];
        for(int i=0;i<Num;i++){
            int y=scanner.nextInt();
            int result=scanner.nextInt();
            Pair pair = new Pair(y,result);
            pairs[i]=pair;
        }
        scanner.close();//读入结束
        Arrays.sort(pairs);//排序ing
        //前缀和
        int[] sum=new int[Num+1];
        sum[0]=0;
        for(int i=1;i<=Num;i++){
            sum[i]=sum[i-1]+pairs[i-1].getY();
//            System.out.println(sum[i]);//可以打印看看
        }

        int max=0;
        int output=0;
        int localsum;
        Set set=new HashSet();
        for(int i=0;i<Num;i++){
            localsum=0;
            int localY=pairs[i].getX();
            if(set.contains(localY))//set去重的必要性在后文解释
                continue;
            set.add(localY);
            int sum1=sum[Num]-sum[i];//自己及之后的 1 的个数
            int sum0=i-sum[i];//不包含自己的之前的 0 的个数
            localsum+=sum0+sum1;//得分！
//            System.out.println(localY+" : "+localsum);//也可以打印看看
            if(localsum>=max){
                max=localsum;
                output=localY;
            }
        }
        System.out.println(output);

    }
    static class Pair implements Comparable{
        private int x;
        private int y;
        public Pair(int x,int y){
            this.x=x;
            this.y=y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public int compareTo(Object o) {//丑陋的比较方法，这样就可以用Arrays.Sort了
            return Integer.compare(this.getX(),((Pair)o).getX());
        }
    }
}

Set去重的正确性

对于得分相同的同学来说，有的挂科了，有的没挂科。 对于样例输入：有两个得分为1 的，前者挂科了，后者没有。用前者计算，sum = 5；后者，sum = 6；后者甚至比正确输出3还要大。 对于后者来说，sum0 = 2，这显然是不对的，因为前面和自己分数相同的人，按照阈值不应该挂科却算上了。对于前者来说，后面都是得分大于等于自己的，所以1都应该算上。 我们换一种情况，假设相同分数数据变成了前者是1未挂科，后者是0挂科了。对于前者来说，后面的0是错误数据，没有加上，因此正确。对于后者来说，前者的1是正确的，但是却没加上，是错误的。 由此看来，只有前者的结果是正确的！！！所以我们后面分数重复的，答案是不一定正确的，我们用Set记录一下这个得分第一次出现了，后面就都不能算了。 以上。