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

题目背景

考虑到安全指数是一个较大范围内的整数、小菜很可能搞不清楚自己是否真的安全，顿顿决定设置一个阈值 θ，以便将安全指数 y 转化为一个具体的预测结果——“会挂科”或“不会挂科”。

因为安全指数越高表明小菜同学挂科的可能性越低，所以当 y≥θ 时，顿顿会预测小菜这学期很安全、不会挂科；反之若 y<θ，顿顿就会劝诫小菜：“你期末要挂科了，勿谓言之不预也。”

那么这个阈值该如何设定呢？顿顿准备从过往中寻找答案。

题目描述

具体来说，顿顿评估了 m 位同学上学期的安全指数，其中第 i（1≤i≤m）位同学的安全指数为$y_i$，是一个 $[0,10^8]$ 范围内的整数；同时，该同学上学期的挂科情况记作 $result_i∈0,1$，其中 0 表示挂科、1 表示未挂科。

相应地，顿顿用 $predict_θ(y)$ 表示根据阈值 θ 将安全指数 y 转化为的具体预测结果。

如果 $predict_θ(y_j) $与 $result_j$ 相同，则说明阈值为 θ 时顿顿对第 j 位同学是否挂科预测正确；不同则说明预测错误。

\[\mathrm{predict}_{\theta} ( y ) = \left\{
\begin{array}{cc}
0& {(y < \theta)}
\\1& {(y \ge \theta)}
\end{array}
\right.
\]

最后，顿顿设计了如下公式来计算最佳阈值 θ∗：

\[\theta^* = \max { \mathop{\mathrm{argmax} }\limits_{\theta \in { y_i } } \sum\limits_{j=1}^{m} ( \mathrm{predict}_{\theta} ( y_j ) == result_j ) }
\]

该公式亦可等价地表述为如下规则：

最佳阈值仅在 $y_i$中选取，即与某位同学的安全指数相同；
按照该阈值对这 m 位同学上学期的挂科情况进行预测，预测正确的次数最多（即准确率最高）；
多个阈值均可以达到最高准确率时，选取其中最大的。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 m。

接下来输入 m 行，其中第 i（1≤i≤m）行包括用空格分隔的两个整数$y_i$和 $result_i$，含义如上文所述。

输出格式

输出到标准输出。

输出一个整数，表示最佳阈值 $\theta^*$。

样例1输入

样例1输出

样例1解释

按照规则一，最佳阈值的选取范围为 0,1,3,5,7。

θ=0 时，预测正确次数为 4；

θ=1 时，预测正确次数为 5；

θ=3 时，预测正确次数为 5；

θ=5 时，预测正确次数为 4；

θ=7 时，预测正确次数为 3。

阈值选取为 1 或 3 时，预测准确率最高；

所以按照规则二，最佳阈值的选取范围缩小为 1,3。

依规则三，$\theta^*=max1,3=3$。

样例2输入

8

5 1

5 0

5 0

2 1

3 0

4 0

100000000 1

1 0

样例2输出

100000000

子任务

70% 的测试数据保证 $m≤200$；

全部的测试数据保证 $2≤m≤10^5$。

错误代码

#include<stdio.h>

int main(){

    int  m,i ,j,max,sum=0;

    long int y[200],thta,sumi=0;

    int  r[200],p=0;

    scanf("%d",&m);

    while(i<m){

        scanf("%ld %d",&y[i],&r[i]);

        i++;

    }

    for (i=0;i<m;i++){

        max=0;

        thta=y[i];

        for(j=0;j<m;j++){

                if(y[j]<thta){

                    p=0;

                }else{

                    p=1;

                }

                if(r[j]==p){

                    max ++;

                }

        }

        if(max>sum||max==sum){

            sum=max;

            sumi=thta;

        }

    }

    printf("%ld", sumi);

    return 0;

}

参考思路1:前缀和

转载自：https://blog.csdn.net/qq_43464088/article/details/112080044

将时间复杂度从$O(m^2)$降到$O(m)$;
解题思路:先对数据按照安全指数yi进行升序排序，然后求出比yi小的0的个数，比yi大的1的个数;
题目数据规模m为1e5，如果用暴力两层for循环是会超时的，只能通过70%的数据，不能拿满分;

前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。

最简单的一道题就是给定 n 个数和 m 次询问，每次询问一段区间的和。求一个 O(n + m) 的做法。

用 O(n) 前缀和预处理，O(m) 询问。

for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];　　//O(n)

while(m--)　　　　　　　　//O(m)

 {

     int L, R; scanf("%d%d", &L, &R);

     printf("%d\n", sum[R] - sum[L - 1]);

 }

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,Max=0,res;

int sum[N]={0};

set<int>st;

pair<int,int>pr[N];

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)

	{

		int a,b;

		cin>>a>>b;

		pr[i]=make_pair(a,b);

	}

	sort(pr+1,pr+n+1);//1.先排序

	for(int i=1;i<=n;i++)

		sum[i] =sum[i-1]+ pr[i].second;//2.求挂科情况前缀和

	for(int i=1;i<=n;i++)

	{

		int a=pr[i].first;//选取阈值

		if(st.count(a)) continue;//set去重

		st.insert(a);

		int yuce1 = sum[n]-sum[i-1];//大于等于阈值时，应统计预测结果中为1的个数

		int yuce0 = i-1-sum[i-1];//小与阈值时，应统计预测结果中为0的个数

		int yuce = yuce1+ yuce0;//合计预测正确次数

		if(yuce >= Max) {

			Max=yuce;

			res=a;

		}

	}

	cout<<res;

	return 0;

}

参考思路2

转载自：https://blog.csdn.net/qq_38632614/article/details/111934286

#include<iostream>

#include<algorithm>

using namespace std;

typedef struct Node{

	int theta;

	int result;

}Node;

bool cmp(Node a,Node b){

	return a.theta<b.theta;

}

int main(){

	int m;

	Node node[100005];

	int flag0[100005]={0}; //记录小于每个位置点阈值的result=0的个数

	int flag1[100005]={0}; //记录大于等于每个位置点阈值的result=1的个数 

	/*--输入--*/

	cin>>m;

	for(int i=0;i<m;i++){

		cin>>node[i].theta>>node[i].result;

	}

	sort(node,node+m,cmp); //输入后排序 

	int i=0,j=1;

	int temp0=0,temp1=0;

	/*--统计小于每个阈值的result=0的个数--*/

	while(j<m){

		if(node[j].theta==node[i].theta){

			j++;

			continue;

		}

		int temp=0;

		while(i<j){

			if(node[i].result==0)temp++;

			flag0[i]=temp0;

			i++;

		}

		temp0+=temp;

	}

	while(i<j){

		flag0[i]=temp0;

		i++;

	}

	/*--以上统计小于每个阈值的result=0的个数--*/

	/*--以下统计大于等于每个阈值的result=1的个数--*/

	for(int i=0;i<m;i++){

		if(node[m-1-i].result==1){

			temp1++;

		}

		flag1[m-1-i]=temp1;

	}

	//根据flag0和flag1计算每个阈值的准确个数，输出最大的对应的阈值

	int ans=0,num=0;

	for(int i=0;i<m;i++){

		if(flag0[i]+flag1[i]>=num){

			num=flag0[i]+flag1[i];

			ans=node[i].theta;

		}

	}

	cout<<ans;

}

巴特西

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