关键：因为特征是一维且阈值只按大小划分，所以只需在相邻不同特征值之间、以及两端考虑切分点。重复特征值的样本不可被阈值拆分，需整组一起在同侧。
做法：
- 将样本按特征 $x$ 升序排序。
- 预处理前缀计数 $\text{prefL}(i)$ ：排序后前 $i$ 个（含 $i$ ）中标签等于 $L$ 的数量。
- 预处理后缀计数 $\text{sufR}(i)$ ：排序后从 $i$ 到末尾中标签等于 $R$ 的数量。
- 只在每个“特征值分组的末尾”作为切分（记该位置为 $i$ ）计算

P3528.第二题-阈值最优的决策树

1000ms

Difficulty: 3

所属公司 : 华为

算法与标签>双指针

题目内容

决策树生成算法递归地产生决策树，直到不能继续下去为止，在这个过程中，最关键的是确定每个节点的阈值。一种传统方法是划分之后，需要使得数据集的熵减最大化。

而小明同学面对的问题是一个基座问题：只有一个特征的数据集的二分类问题。如果构建出二叉树，那么将形如：”一个根节点配两个儿子节点“的结构。

在这种问题下，小明希望通过一个更加简洁的策略来获得结果：枚举阈值，得到验证集上的最优的准确率。请问给定验证集，需要设定怎样的阈值使得准确率最大化。

请输出小 $A$ 通过他提出的寻找阈值的策略，在验证集上可以达到的最优准确率

第一行一个整数 $M(1<=M<=10^5)$ 表示验证集条数

随后 $M$ 行为验证集特征和 $label$ ，每行 $2$ 个整数，第一个数为该条数据的特征，最后一个整数为该条数据的 $label \in [0,1]$ 。

随后一行两个整数 $L,R$ 分别代表左子树和右子数的 $label$ , $L\neq R且L,R\in[0,1]$

第一行，一个浮点数，为验证集可达到的最优准确率，四舍五入保留小数点后 $3$ 位。

输入

输出

0.800

说明

设定阈值 $=5$ , 那么所有样本进入左子树，被归类为0 ，准确率为 $\frac{4}{5}=0.8$ , 注意保留三位小数

输入

输出

1.000

说明

设定阈值 $=3$ , 那么样本 $1,2,3$ 进入左子树，被归类为1 ，样本 $4,5,6$ 进入右子树，被归类为 $0$ ，全部分类正确，准确率为 $1$

提示

$本题准确率的计算方法为:\frac{预测正确的样本个数}{总样本个数}$

输入

预期输出（选填）