算法标签

双指针（二分优化）、概率计算、对数变换、前缀和优化、单调性分析

问题分析

本题要求从长度为 $N$ 的公牛列表中，选择一段相邻区间，使得恰好有一只公牛接受邀请的概率最大。核心是将概率计算转化为可高效求解的数学表达式，利用单调性优化搜索过程。

关键公式推导

1. 恰好一个接受的概率：对于区间 $[L, R]$，概率为 $\sum_{k=L}^R \left[ p_k \cdot \prod_{i=L,i \neq k}^R (1-p_i) \right]$。
2. 公式变形：提取公共因子 $\prod_{i=L}^R (1-p_i)$，转化为 $\left( \prod_{i=L}^R (1-p_i) \right) \cdot \sum_{k=L}^R \frac{p_k}{1-p_k}$，记为 $P(L,R) = Q(L,R) \cdot S(L,R)$（$Q$ 为乘积项，$S$ 为求和项）。

单调性关键观察

• 求和项 $S(L,R) = \sum_{k=L}^R \frac{p_k}{1-p_k}$ 是关于 $R$ 的单调递增函数（每项均为正）。
• 乘积项 $Q(L,R) = \prod_{i=L}^R (1-p_i)$ 是关于 $R$ 的单调递减函数（每项均在 $(0,1)$ 区间）。
• 两者乘积 $P(L,R)$ 先增后减，存在唯一最大值，可通过二分或双指针找到每个左端点 $L$ 对应的最优右端点 $R$。

核心算法思路

1. 预处理前缀和与前缀对数和

• 定义 $s[i] = \sum_{k=1}^i \frac{p_k}{1-p_k}$，则 $S(L,R) = s[R] - s[L-1]$，通过前缀和快速计算。
• 定义 $t[i] = \sum_{k=1}^i \log(1-p_k)$，则 $\log Q(L,R) = t[R] - t[L-1]$，利用对数将乘积转化为求和，避免浮点数精度丢失。

2. 二分查找最优右端点

• 对每个左端点 $L$，二分查找最大的 $R$ 使得 $S(L,R) \leq 1$（基于函数单调性，此时乘积项与求和项的乘积接近最大值）。
• 验证该 $R$ 及相邻位置，计算 $P(L,R) = \exp(t[R] - t[L-1]) \cdot (s[R] - s[L-1])$，更新全局最大值。

3. 精度处理与结果输出

• 全程使用浮点数计算，通过对数变换和指数还原避免乘积溢出。
• 最终结果乘以 $10^6$ 后下取整，满足题目输出要求。

复杂度分析

• 时间复杂度：$O(N \log N)$。每个左端点对应一次二分查找，每次二分复杂度为 $O(\log N)$，总迭代次数为 $O(N)$。
• 空间复杂度：$O(N)$。存储前缀和数组 $s$、前缀对数和数组 $t$ 及概率数组 $p$，均为线性空间。

总结

本题核心是将概率问题转化为数学函数分析，利用单调性简化最优解搜索。通过前缀和优化求和计算、对数变换优化乘积计算，结合二分查找高效定位最优区间，在 $O(N \log N)$ 复杂度内解决了 $N \leq 10^6$ 的大规模数据问题，兼顾了效率与精度。