#P2020122. 期末预测之最佳阈值(数学公式没做好)

期末预测之最佳阈值(数学公式没做好)

期末预测之最佳阈值(数学公式没做好)

题目描述

题目背景

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

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

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

题目描述

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

相应地,顿顿用predictθ(y)表示根据阈值θ将安全指数y转化为的具体预测结果。 如果predictθ(yj)与resultj相同,则说明阈值为θ时顿顿对第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 ) }$$

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

最佳阈值仅在yi中选取,即与某位同学的安全指数相同;

按照该阈值对这m位同学上学期的挂科情况进行预测,预测正确的次数最多(即准确率最高);

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

输出一个整数,表示最佳阈值θ∗。

数据范围

(原站未提供,导入后需人工补齐)

样例

6
0 0
1 0
1 1
3 1
5 1
7 1
3
样例1解释
按照规则一,最佳阈值的选取范围为 0 ,1,3,5,7。

 时,预测正确次数为 ;

 时,预测正确次数为 ;

 时,预测正确次数为 ;

 时,预测正确次数为 ;

 时,预测正确次数为 。

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

依规则三,
。
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0
100000000

提示

子任务

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

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