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

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

问题描述
试题编号： 202012-2
试题名称： 期末预测之最佳阈值
时间限制： 1.0s
内存限制： 512.0MB

题目背景

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

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

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

题目描述

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

相应地，顿顿用 predictθ(y) 表示根据阈值 θ 将安全指数 y 转化为的具体预测结果。
如果 predictθ(yj) 与 resultj 相同，则说明阈值为 θ 时顿顿对第 j 位同学是否挂科预测正确；不同则说明预测错误。

predictθ(y)={0 (y<θ)，1(y≥θ)}

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

θ∗=maxargmaxθ∈yi⁡∑j=1m(predictθ(yj)==resultj)

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

1. 最佳阈值仅在 yi 中选取，即与某位同学的安全指数相同；

2. 按照该阈值对这 m 位同学上学期的挂科情况进行预测，预测正确的次数最多（即准确率最高）；

3. 多个阈值均可以达到最高准确率时，选取其中最大的。

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

输出一个整数，表示最佳阈值 θ∗。
样例1输入

6
0 0
1 0
1 1
3 1
5 1
7 1

样例1输出

3

样例1解释

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

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

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

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

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

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

阈值选取为 1 或 3 时，预测准确率最高； 所以按照规则二，最佳阈值的选取范围缩小为 1,3。

依规则三，θ∗=max1,3=3。

样例2输入

   85 15 05 02 13 04 0100000000 11 0

样例2输出

100000000

子任务

思路

看直播课看到的方法是用前缀和，以判断数为基准画线，计算该线之前的0的个数与该线之后的1的个数，得到的就是该数判断正确的总个数；用pair存储的二元组，用s[2][N]分别存储0和1的前缀和，代码大大缩短了

更新的AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
#define x first
#define y second
typedef pair<int,int> PII;
PII p[N];
int s[2][N];//s[0][i]:代表第i个数前面有多少个0，s[1][i]：代表第i个数前面有多少个1 
int main(){scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d%d",&p[i].x,&p[i].y);sort(p+1,p+n+1);//将二元组排序 for(int i = 0;i < 2;i++)for(int j = 1;j <= n;j++)s[i][j] = s[i][j-1] + (p[j].y==i);int maxn = -1 , ans;for(int i = 1;i <= n;i++){int tp = s[0][i-1] + s[1][n] - s[1][i-1];if(tp >= maxn) maxn = tp,ans = p[i].x;while(i+1<=n && p[i].x==p[i+1].x)	//会出现1 0,1 1这种情况，应该算除了该数之外的前缀和，而不能算紧邻的前缀和 i++;}printf("%d",ans);
}

好久没有更新博客了，这学期天梯赛后就一直在搞其他的事情，很久没有刷题了，马上又要CSP认证了，赶快用假期时间刷刷题
这是去年12月份CSP时候的第二题，当时被这道题卡住了，后三个测试点一直过不去，最后170收尾，需要用更好的方法去做才能不运行超时，后三个测试数据应该是因为数据多导致了超时，显然用O（n^2）的方法不可行
那么通过分析样例，是不是对于每一个阈值的正确判断个数，只需要看前一个（比它小一个）阈值的学生的result情况就可以，比它小的阈值只有result=0才是正确的，所以如果前一个阈值的学生有一个为0，该阈值的正确判断就在前一个阈值的正确判断个数的情况下+1,；为1的话，就-1

AC代码：

#include<bits/stdc++.h>
using namespace std; 
struct people{int y,result;
}pp[100005];
bool cmp(struct people pp1,struct people pp2){return pp1.y < pp2.y;
}
int main(){int m;cin >> m;for(int i = 0;i < m;i++){cin >> pp[i].y >> pp[i].result;}sort(pp,pp+m,cmp);int stdd = pp[0].y;int max = 0;for(int i = 0;i < m;i++){if(pp[i].y < stdd && pp[i].result == 0){max++;}else if(pp[i].y >= stdd && pp[i].result == 1){max++;}}int index = 0;int tp = max;for(int i = 1;i < m;i++){if(stdd == pp[i].y){continue;}stdd = pp[i].y;	//当前阈值int temp = i-1;	while(pp[temp].y == pp[i-1].y){//找前一个阈值if(pp[temp].result==0){tp++;}else{tp--;}temp--;}if(tp >= max){max = tp;index = pp[i].y;}}cout << index << endl;
}

这篇关于CSP 202012-2期末预测之最佳阈值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---