题目解析：考试策略优化

问题概述

Marysia 参加一场包含 n 道题的考试，每道题有三种可能结果：

• 回答正确：+1 分
• 回答错误：-1 分
• 不回答：0 分

要通过考试，总分必须至少达到 t 分。对于每道题 i，Marysia 知道答案正确的概率为 pᵢ。她需要决定回答哪些题目、跳过哪些题目，以最大化通过考试的概率。

关键观察与数学建模

1. 得分模型

如果 Marysia 选择回答 k 道题，设其中 x 道回答正确，那么：

• 总得分 S = x × 1 + (k - x) × (-1) = 2x - k
• 通过条件：2x - k ≥ t ⇒ x ≥ ⌈(t + k)/2⌉

2. 最优策略结构

重要结论：最优解总是选择正确概率最高的题目子集。

证明思路：如果存在最优解包含概率较低的题目而排除概率较高的题目，交换这两道题不会降低通过概率。

3. 概率计算

对于选择前 k 道最高概率的题目：

• 需要至少答对 m = ⌈(t + k)/2⌉ 道题
• 通过概率 = P(在前 k 题中答对至少 m 题)

算法挑战与优化

挑战

直接计算所有可能 k 的通过概率需要 O(n²) 时间，对于 n ≤ 50000 不可行。

优化思路

1. 概率排序

首先将题目按正确概率降序排序，确保只考虑前缀子集。

2. 动态规划优化

使用滑动窗口技术聚焦在概率分布的主要区域：

• 核心思想：概率分布集中在期望值附近，尾部概率极小可忽略
• 维护当前处理题目的期望正确数 sum = Σpᵢ
• 窗口范围：[sum - B, sum + B]，其中 B 为常数（如 670）
• 只更新窗口内的概率状态，大幅减少计算量

3. 状态转移

对于每道新题目 i：

• 更新概率分布：dp[j+1] += dp[j] × pᵢ（答对情况）
• 同时更新：dp[j] ×= (1 - pᵢ)（答错情况）

4. 边界处理

特殊处理窗口边界情况，确保概率守恒。

5. 答案更新

对于每个前缀长度 k，计算：

• 需要的最小正确题数 m = ⌈(t + k)/2⌉
• 如果 m 在窗口内，更新最大通过概率

算法优势

时间复杂度

• 排序：O(n log n)
• 动态规划：O(n × B)，其中 B 为常数
• 总复杂度：O(n log n + nB)，对于 n ≤ 50000 可接受

空间复杂度

O(n)，使用一维 DP 数组

精度保证

• 聚焦概率分布主要区域，忽略极小概率尾部
• 使用 double 类型保证数值精度
• 满足题目要求的 10⁻⁶ 绝对误差

样例分析

样例 1

n=5, t=2
概率: [0.77, 0.85, 0.75, 0.98, 0.6]

排序后：[0.98, 0.85, 0.77, 0.75, 0.6]

最优策略：回答前 4 题

• 需要至少 ⌈(2+4)/2⌉ = 3 题正确
• 计算概率 ≈ 0.8798125

样例 2

n=5, t=3  
概率: [0.3, 0.01, 0.2, 0.15, 0]

排序后：[0.3, 0.2, 0.15, 0.01, 0]

最优策略：回答前 3 题

• 需要全部正确：0.3 × 0.2 × 0.15 = 0.009

总结

该问题通过结合贪心排序和优化的动态规划，巧妙解决了大规模概率计算问题。核心创新在于利用概率分布的局部性，通过滑动窗口技术将复杂度从 O(n²) 降为 O(nB)，在保证精度的同时实现高效计算。

算法体现了以下重要思想：

1. 问题结构分析：发现最优解的结构特性
2. 概率分布特性：利用期望附近的集中性
3. 计算优化：通过窗口技术避免不必要的计算
4. 精度权衡：在计算效率和数值精度间取得平衡