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

2023-01-01

题目

【题目背景】考虑到安全指数是一个较大范围内的整数、小菜很可能搞不清楚自己是否真的安全，顿顿决定设置一个阈值，以便将安全指数y转化为一个具体的预测结果——“会挂科”或“不会挂科”。因为安全指数越高表明小菜同学挂科的可能性越低，所以当$y≥\theta$时，顿顿会预测小菜这学期很安全、不会挂科；反之若$y<\theta$，顿顿就会劝诫小菜：“你期末要挂科了，勿谓言之不预也。” 那么这个阈值该如何设定呢？顿顿准备从过往中寻找答案。

【题目描述】具体来说，顿顿评估了m位同学上学期的安全指数，其中第 $i(1\leq i\leq m)$位同学的安全指数为yi，是一个[0,10^8]范围内的整数；同时，该同学上学期的挂科情况记作$result_i\in 0,1$，其中0表示挂科、1表示未挂科。相应地，顿顿用$predict_\theta(y)$表示根据阈值$\theta$将安全指数 y 转化为的具体预测结果。如果$predict_\theta(y_j)$与 $result_j$相同，则说明阈值为$\theta$时顿顿对第 j 位同学是否挂科预测正确；不同则说明预测错误。

$$
{predict}_\theta\left(y\right)=\left{
\begin{aligned}
0 \qquad (y<θ)\
1 \qquad (y≥θ)
\end{aligned}
\right.
$$

最后，顿顿设计了如下公式来计算最佳阈值$\theta^*$:

$$
\theta^*={\underset{\theta\in y_i}{\arg\max}\sum_{j=1}^{m}(predict_\theta(y_i)==result_j)}
$$

该公式亦可等价地表述为如下规则： 1.最佳阈值仅在yi 中选取，即与某位同学的安全指数相同； 2.按照该阈值对这 m 位同学上学期的挂科情况进行预测，预测正确的次数最多（即准确率最高）； 3.多个阈值均可以达到最高准确率时，选取其中最大的。

【输入格式】从标准输入读入数据。输入的第一行包含一个正整数。接下来输入m行，其中第$i(1\leq i\leq m)$行包括用空格分隔的两个整数 yi和resulti，含义如上文所述。

【输出格式】输出到标准输出。输出一个整数，表示最佳阈值。

【样例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$。

代码

//前缀和
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
struct node {
    int y;
    int result;
}a[N];

bool cmp(node A,node B)
{
    return (A.y<B.y);
}

int main()
{
    int m,t,j=0,num=0,cnt=0,ans=0;
    int b[N]={0};
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a[i].y>>a[i].result;
    }
    sort(a,a+m,cmp);
    b[0]=a[0].result;
    for(int i=1;i<m;i++)
    {
        b[i]=b[i-1]+a[i].result;
    }
    for(int i=0;i<m;i++)
    {
        if(i==0)
        {
            t=0;
            j=-1;
        }
        else
        {
            j=i-1;
            while(a[j].y==a[i].y){j--;}
            t=b[j];
        }
        num=j+1-t+b[m-1]-t;
        //cout<<a[i].y<<' '<<num<<endl;
        if(num>=cnt)
        {
            cnt=num;
            ans=a[i].y;
        }
    }
    cout<<ans<<endl;
    return 0;

}