题解：P14763 [Opoi 2025] CCD 的赌局
SuyctidohanQ
·
·
题解
对于任意一个固定的赔率 A（则 B = T - A），在第 i 轮的赔付金额为：
\max(A \times a_i,(T-A)\times b_i)
当 A \times a_i \ge (T-A) \times b_i 时，取左边，否则取右边。整理不等式得：
A \ge T \times \frac{b_i}{a_i+b_i}
定义阈值 p_i = T \times \frac{b_i}{a_i + b_i}。那么：
- 当 A \ge p_i 时，赔付 A \times a_i。
- 当 A < p_i 时，赔付 (T-A) \times b_i。
对于前 k 轮，我们需要找到最优的 A_1 使得 \sum_{i=1}^k \max(A_1 \times a_i, (T-A_1) \times b_i) 最小。
设 S_a = \sum a_i，S_b = \sum b_i。考虑将 p_i 排序后，随着 A 从 0 增加到 T：
- 初始时，所有轮都取 (T-A) \times b_i，总赔付为 (T-A) \times S_b。
- 当 A 超过某个 p_i 时，第 i 轮改为取 A \times a_i。
因此总赔付函数是关于 A 的分段线性函数，且是凸函数（先减后增），最小值在某个转折点或端点处取得。