[数据结构与算法]csp 期末预测之最佳阈值 题解 （排序+前缀和）

这个题说通俗点就是，从y里面找个阈值，然后看y，如果y比这个阈值大，则预测是过了，如果y比这个阈值小，则预测是没过，然后找出预测正确的最大阈值。这个题如果没有什么好的思路，使用暴力解决也是能过百分之七十。

大致思路：
???因为要选出比阈值大的，还要选出比阈值小的，所以就需要先对数据进行排序，这样在选的时候，这个数之前的都是比它小的，之后的都是比他大的。因为对每一个阈值来说，他前面的数都是没过，后面的数都是过了，所以我们需要算每个result所对应的前缀和，然后根据这个前缀和来判断是多少人过了，多少人没过。具体的实现就详细看代码吧。

static class Data {
        public int key;
        public int value;

    }

因为y和result算是绑定在了一起，所以就是将两个弄到一个类里面，排序比较好排

 		for(int i=0;i<m;i++) {
            Data data=new Data();
            data.key=sc.nextInt();
            data.value=sc.nextInt();
            if(data.value==1)
                total++;//算出一共有多少人过
            array.add(data);
        }
        array.sort((o1, o2) -> o1.key-o2.key);

这块就是将数据按照key进行从小到大排序

 		int[] sum=new int[m];
        int t=0,index=0;
        for(Data data:array){
            t+=data.value;
            sum[index++]=t;
        }

sum是用来求前缀和的，sum[i]表示前i个人有多少个过的

	    index=0;
        int max=0,max_k=0,pre_key=-1;
        for(Data data:array) {
            if(data.key==pre_key){//如果碰到相等的就直接跳过，因为前面已经算过了
                index++;
                continue;
            }
            int temp;
            if(index==0){//当以第一个数为阈值的时候，后面的数都比他大，所以应该预期值都为1，它答对的就是本来就应该过的，所以就是total
                temp=total;
            }else{//到index其实有index+1个人，但是因为是以它的上边为分界点，所以就是有index个人，index-实际过了的，才是实际没过的，实际没过的就是猜对的
                temp=(index-sum[index-1])+(total-sum[index-1]);
            }
            if(temp>=max){
                max=temp;
                max_k=data.key;
            }
            pre_key=data.key;
            index++;

        }

index表示现在是到第几个人了。如果key相等，则index++，剩下的不执行。
要从第一个人开始遍历，第一个人就是index==0，所以第一个人就没有预期为0的，所有的数都是预期为1，但是实际只有total个1，所以当index ==0的时候，答对了total个。当index！=0的时候，本来是有index+1个人，但是第index+1这个人要算在后边（因为y大于等于阈值都为1），所以前面就有index个人，按预测来说就应该有index个0，但是前面现在有sum[index-1]个1，表示这sum[index-1]都是猜错的，所以阈值前面预测对的是有index-sum[index-1]个，而total-sum[index-1]就表示总的过的人数减去前面过的人数，所以就是后面过的人数，所以
temp=(index-sum[index-1])+(total-sum[index-1]),加号前面的表示阈值之前没过的，加号之后表示阈值之后过了的，这两个加起来就能找到总共判对的。
主要就是要理解这个temp的表达式。
接下来就看完整代码吧：

import java.util.*;

public class Main {
    static class Data {
        public int key;
        public int value;

    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int total=0;
        ArrayList<Data> array=new ArrayList<>();
        for(int i=0;i<m;i++) {
            Data data=new Data();
            data.key=sc.nextInt();
            data.value=sc.nextInt();
            if(data.value==1)
                total++;//算出一共有多少人过
            array.add(data);
        }
        array.sort((o1, o2) -> o1.key-o2.key);//按照key进行排序
        int[] sum=new int[m];//sum是用来求前缀和的，sum[i]表示前i个人有多少个过的
        int t=0,index=0;
        for(Data data:array){
            t+=data.value;
            sum[index++]=t;
        }

        index=0;
        int max=0,max_k=0,pre_key=-1;
        for(Data data:array) {
            if(data.key==pre_key){//如果碰到相等的就直接跳过，因为前面已经算过了
                index++;
                continue;
            }
            int temp;
            if(index==0){//当以第一个数为阈值的时候，后面的数都比他大，所以应该预期值都为1，它答对的就是本来就应该过的，所以就是total
                temp=total;
            }else{//到index其实有index+1个人，但是因为是以它的上边为分界点，所以就是有index个人，index-实际过了的，才是实际没过的，实际没过的就是猜对的
                temp=(index-sum[index-1])+(total-sum[index-1]);
            }
            if(temp>=max){
                max=temp;
                max_k=data.key;
            }
            pre_key=data.key;
            index++;

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