【CSP试题回顾】202012-2-期末预测之最佳阈值

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

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

关键点：时间复杂度优化

时间复杂度的优化主要来自于有效地利用排序和累计的分类正确数来避免对每个可能的决策阈值进行完全的暴力枚举。

1.暴力枚举（70分）

在暴力枚举方法中，对每一个可能的决策阈值 y，我们都需要遍历所有数据点来确定在此阈值下的分类正确数目。这意味着如果有 n 个数据点，且有 m 个不同的决策阈值，则时间复杂度为 $O (mn)$ 。这是因为对于每一个决策阈值，我们都重新计算整个数据集中的正确分类数量。

2.优化方法（100分）

相比之下，优化方法利用了排序和动态更新的概念，大幅降低了时间复杂度：

排序和初始化：首先，通过排序（这通常涉及在输入阶段隐式完成，因为我们使用的是 map 结构，它会根据 key（y 值）进行排序），我们可以确保在遍历数据结构时是按照决策阈值的顺序进行的。初始化部分（包括第一次遍历）的时间复杂度为 $O (n)$ ，因为它基于数据点的总数。
单次遍历更新：在之后的处理中，对于每个后续的决策阈值 y，我们不需要重新计算整个数据集来确定分类正确的数量。相反，我们可以利用上一个阈值的结果，通过简单的加法和减法更新正确分类的数量。因此，对于每一个新的阈值，更新操作仅需要 $O (1)$ 的时间（原因详见下一节）。

解题思路

数据结构定义：
- MyScore 结构用于存储每个决策阈值 y 下，分类结果为 0 和 1 的数量。
- 使用 map<int, MyScore> 来存储每个决策阈值 y 和对应的 MyScore 结构，键是 y，值是 MyScore。
输入处理：
- 通过循环，读取每个数据点的 y 值和实际分类结果 r（0 或 1）。
- 根据读入的 y 和 r，更新对应 y 的 MyScore 结构中的 resultIsZeroNum 或 resultIsOneNum。
初始化和遍历处理：
- 定义 ac 为当前决策阈值 y 下分类正确的数据点数目，acMax 为最大的分类正确数目，acMaxY 为使得 acMax 最大的 y 值。
- 在开始遍历 scoreMap 之前，预先处理第一个元素（最小的 y 值），因为基于问题的设定，因为scoreMap中的第一个元素是y的最小值，当y为最小值时，此时 $\theta$ 小于等于所有的y，因此所有 $res u lt = 1$ 都正确，也就是输入中1的总数。
- 遍历 scoreMap，对于每一个不同的 y 值（除了第一个），计算在此阈值下的分类正确数目 ac。计算方法为从上一个 y 的正确数目 ac 减去在上一个阈值下被正确分类为 1 的数量（这些现在被分类为错误），然后加上在上一个阈值下被错误分类为 0 的数量（这些现在被分类为正确）。
  - 【注意】这样做的本质是：y的改变只影响其前一个元素 $p re d i c t$ 的结果，而不影响其他的，因此不要用遍历所有的 $p re d i c t$ ，从而只需要计算一次，大大降低了时间复杂度。
更新最优解：
- 在遍历每个 y 时，如果当前的 ac（分类正确的数量）大于或等于 acMax，则更新 acMax 为当前的 ac，并且更新 acMaxY 为当前的 y。

完整代码

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;struct MyScore
{int resultIsZeroNum; // 同一个y下，result为0的数量int resultIsOneNum; // 同一个y下，result为1的数量
};int n, y, r, ac, acMax, acMaxY; // ac:每个y下对应的正确数；acMax:最大ac数；acMaxY:最大ac数对应的y（theta）
map<int, MyScore>scoreMap; // 键-y 值-MyScore（记录y下result为0和1的数量）int main() {cin >> n;for (int i = 0; i < n; i++){cin >> y >> r;if (r)  ac++, scoreMap[y].resultIsOneNum++; // r = 1; 同时统计y_min时的acelse scoreMap[y].resultIsZeroNum++; // r = 0}bool firstTime = 1; // 跳过第一次循环（y_min），因为此时的ac已经在前面统计了pair<int, MyScore> last = *scoreMap.begin(); // it的前一个元素for (auto& it : scoreMap){if (firstTime) {firstTime = 0;acMax = ac; // 初始化acMaxacMaxY = it.first; // 初始化acMaxYcontinue;}ac = ac - last.second.resultIsOneNum + last.second.resultIsZeroNum; // ac的增减本质上是当前元素的前一个元素预测正确性的改变，对其他元素无影响if (ac >= acMax) // 检测更新{acMax = ac;acMaxY = it.first;}last = it; }cout << acMaxY;return 0;
}