一、问题分析与数学建模

1.1 问题本质

这是一道概率期望 + 贪心策略问题，核心在于理解失落的定义并设计最优的项目安排方案。

问题形式化

状态空间：

• 心情：{高兴, 不高兴}
• 初始状态：不高兴（第0天之后）

项目：

• 第 $i$ 个项目：不高兴概率 $p_i = \frac{x_i}{y_i}$，高兴概率 $1-p_i$
• 可用次数：$c_i$

失落定义：

$$\text{失落} \Leftrightarrow \text{昨天高兴} \land \text{今天不高兴} $$

目标：最小化 $k$ 天内失落的期望次数。

---

1.2 核心数学推导

定理 1：失落期望的计算公式

命题：某一天发生失落的期望等于：

$$E[\text{失落}] = P(\text{昨天高兴}) \times P(\text{今天不高兴}) $$

证明： 失落是 0-1 随机变量：

$$E[\text{失落}] = 1 \cdot P(\text{失落}) + 0 \cdot P(\text{不失落}) = P(\text{失落}) $$

由于每天的项目结果相互独立，失落需要两个事件同时发生：

$$P(\text{失落}) = P(\text{昨天高兴}) \times P(\text{今天不高兴}) $$

---

定理 2：连续使用同一项目

命题：连续使用概率为 $p$ 的项目 $m$ 次，从不高兴概率为 $q$ 的状态开始，总失落期望为：

$$E_{\text{total}} = (1-q) \cdot p + (m-1) \cdot (1-p) \cdot p $$

证明：

第 1 次：

• 昨天不高兴概率：$q$，高兴概率：$1-q$
• 今天不高兴概率：$p$
• 失落期望：$(1-q) \times p$

第 2 到第 $m$ 次：

• 昨天的状态就是这个项目的结果（概率 $p$）
• 昨天高兴概率：$1-p$
• 今天不高兴概率：$p$
• 每次失落期望：$(1-p) \times p$
• 共 $m-1$ 次

总期望：

$$E_{\text{total}} = (1-q) \cdot p + (m-1) \cdot (1-p) \cdot p $$

---

定理 3：贪心策略的最优性

问题：在某一步，当前"接口"状态有两个选择：

• 选择概率为 $p_l$ 的项目（左端，概率较大）
• 选择概率为 $p_r$ 的项目（右端，概率较小）

假设之前的状态使得：

• 如果选左端，前一步的不高兴概率为 $q_l$
• 如果选右端，前一步的不高兴概率为 $q_r$

下一步无论如何都要使用概率为 $p_{next}$ 的项目。

分析：

选左端的期望：

$$E_l = (1-q_l) \cdot p_l + (1-p_l) \cdot p_{next}$$

选右端的期望：

$$E_r = (1-q_r) \cdot p_r + (1-p_r) \cdot p_{next}$$

差值：

$$\begin{aligned} E_l - E_r &= (1-q_l)p_l - (1-q_r)p_r + (p_r - p_l)p_{next} \\ &= \ldots \text{（复杂的表达式）} \end{aligned}$$

虽然完整推导复杂，但代码采用的启发式策略是：

贪心准则：当 $q_l + q_r \geq 1$ 时，选择概率较大的（左端）；否则选择概率较小的（右端）。

---

1.3 边界优化策略

关键观察：

第 1 天：

• 初始状态：不高兴
• 无论选什么，都不会失落（因为昨天不高兴）
• 策略：选择概率最小的项目（让她最可能高兴），为后续减少失落

第 $k$ 天：

• 这是最后一天，之后没有失落了
• 策略：选择概率最大的项目（反正后面没有影响了）

中间天数：根据贪心策略动态选择。

---

二、算法设计

2.1 整体策略

预处理：

1. 过滤掉次数为 0 的项目
2. 按不高兴概率降序排序
3. 左指针 $l = 0$（最大概率），右指针 $r = n-1$（最小概率）

初始化：

• 第 1 天：使用右端项目（最小概率）
• 第 $k$ 天：使用左端项目（最大概率）
• 剩余 $k-2$ 天需要安排

贪心填充：

• 维护左端状态 $\text{nowl}$ 和右端状态 $\text{nowr}$
• 根据 $\text{nowl} + \text{nowr}$ 的值决定选择哪一端
• 批量处理相同概率的项目

最后连接： 计算从 $\text{nowl}$ 到 $\text{nowr}$ 的失落期望。

---

2.2 时间复杂度

排序：$O(n \log n)$

主循环：

• 最坏情况：$O(k)$
• 优化后（批量处理）：接近 $O(n)$

总复杂度：$O(n \log n + \min(k, n))$

---

三、代码模块详解

模块 1：输入与预处理

void Main() {
    scanf("%d %d", &n, &k);
    std::vector<std::pair<long double, int>> a(n);
    
    for (int i = 0, x, y; i < n; i++) {
        scanf("%d/%d %d", &x, &y, &a[i].second);
        a[i].first = 1.0 * x / y;  // 计算不高兴概率
        
        // 过滤次数为 0 的项目
        if (!a[i].second)
            n--, i--;
    }
    
    a.resize(n);

数据结构：

• a[i].first：第 $i$ 个项目的不高兴概率 $p_i$
• a[i].second：剩余可用次数 $c_i$

优化点：

• 实时过滤无效项目，减少后续判断
• 使用 long double 保证精度

---

模块 2：特殊情况

if (k == 1) {
    puts("0.000000");
    return;
}

数学依据：

• 只有 1 天，初始状态不高兴
• 失落 = 昨天高兴 $\land$ 今天不高兴
• 没有"昨天高兴"的可能 → 期望 = 0

---

模块 3：排序与初始化

std::sort(all(a), std::greater<>());
int l = 0, r = n - 1;
long double nowl = a[l].first, nowr = a[r].first;
long double ans = 0;
k -= 2;
a[l].second -= 1, a[r].second -= 1;

排序：

• 降序：$a[0]$ 概率最大，$a[n-1]$ 概率最小

边界处理：

• 第 1 天：右端（概率最小） → $\text{nowr} = a[r].\text{first}$
• 第 $k$ 天：左端（概率最大） → $\text{nowl} = a[l].\text{first}$
• 各预留一次，剩余 $k-2$ 天

状态含义：

• $\text{nowl}$：左端当前的不高兴概率（用于后续决策）
• $\text{nowr}$：右端当前的不高兴概率（用于后续决策）

---

模块 4：主循环 - 贪心选择

while (k) {
    // 跳过已用完的项目
    while (!a[l].second)
        l++;
    while (!a[r].second)
        r--;
    
    int delta;
    
    if (nowl + nowr >= 1.0) {
        // 选择左端（概率大）
        // ...
    } else {
        // 选择右端（概率小）
        // ...
    }
}

决策准则：

• 当 $\text{nowl} + \text{nowr} \geq 1.0$ 时：选择左端
• 当 $\text{nowl} + \text{nowr} < 1.0$ 时：选择右端

数学直觉：

• $\text{nowl} + \text{nowr} \geq 1$ 意味着两个状态都比较"坏"
• 此时选择更坏的（左端），利用定理3的贪心策略

---

情况 1：选择左端

if (nowl + nowr >= 1.0) {
    // 选择左端
    if (a[l].first == nowl)
        delta = std::min(k, a[l].second);
    else
        delta = 1;
    
    k -= delta;
    a[l].second -= delta;
    ans = ans + (1 - nowl) * a[l].first 
            + (delta - 1) * (1 - a[l].first) * a[l].first;
    nowl = a[l].first;
}

批量优化：

• 如果新项目概率 = 当前状态：可连续使用 $\delta$ 次
• 否则：只使用 1 次，更新状态

期望计算（根据定理 2）： 设 $p_l = a[l].\text{first}$，使用 $\delta$ 次。

• 第 1 次：$(1 - \text{nowl}) \times p_l$
• 后续 $\delta - 1$ 次：$(1 - p_l) \times p_l$ 每次

总期望：

$$(1 - \text{nowl}) \cdot p_l + (\delta - 1) \cdot (1 - p_l) \cdot p_l $$

状态更新：

nowl = a[l].first;

---

情况 2：选择右端

else {
    // 选择右端
    if (a[r].first == nowr)
        delta = std::min(k, a[r].second);
    else
        delta = 1;
    
    k -= delta;
    a[r].second -= delta;
    ans = ans + (1 - a[r].first) * nowr 
            + (delta - 1) * (1 - a[r].first) * a[r].first;
    nowr = a[r].first;
}

对称逻辑：

设 $p_r = a[r].\text{first}$，使用 $\delta$ 次。

期望计算：

注意：这里的公式略有不同！

(1 - a[r].first) * nowr

这里 $(1 - p_r) \times \text{nowr}$ 的含义：

• 这是算法的巧妙之处
• 由于双端填充的对称性，期望计算方式有所调整

根据定理 2 的对称形式，总期望为：

$$(1 - p_r) \cdot \text{nowr} + (\delta - 1) \cdot (1 - p_r) \cdot p_r $$

状态更新：

nowr = a[r].first;

---

模块 5：最后连接

ans = ans + (1 - nowl) * nowr;
printf("%.6Lf\n", ans);

最后一步：

• 从 $\text{nowl}$ 状态到 $\text{nowr}$ 状态
• 失落期望：$(1 - \text{nowl}) \times \text{nowr}$

含义：

• $\text{nowl}$：倒数第二步的不高兴概率
• $1 - \text{nowl}$：倒数第二步的高兴概率
• $\text{nowr}$：最后一步的不高兴概率
• 期望：$(1 - \text{nowl}) \times \text{nowr}$

---

四、样例验证

样例 1：$n=1, k=2$, $p=0/1=0$

项目：不高兴概率 = 0（必定高兴）

分析：

• 第 1 天：必定高兴
• 第 2 天：必定高兴
• 从不高兴 → 高兴：无失落
• 从高兴 → 高兴：无失落
• 答案：0

---

样例 2：$n=1, k=2$, $p=1/1=1$

项目：不高兴概率 = 1（必定不高兴）

分析：

• 第 1 天：必定不高兴
• 第 2 天：必定不高兴
• 从不高兴 → 不高兴：无失落
• 答案：0

---

样例 3：$n=1, k=2$, $p=1/2=0.5$

项目：不高兴概率 = 0.5

执行过程：

1. 排序后：$a[0] = (0.5, 3)$
2. $l = 0, r = 0$（只有一个项目）
3. $\text{nowl} = 0.5, \text{nowr} = 0.5$
4. $k -= 2$ → $k = 0$，跳过循环
5. 最后连接：$\text{ans} = (1 - 0.5) \times 0.5 = 0.25$

数学验证：

所有可能的情况（等概率）：

1. 不高兴 → 不高兴：无失落
2. 不高兴 → 高兴：无失落
3. 高兴 → 不高兴：失落 1 次
4. 高兴 → 高兴：无失落

但初始状态是不高兴，所以：

1. 第1天不高兴，第2天不高兴：概率 $0.5 \times 0.5 = 0.25$，失落 0 次
2. 第1天不高兴，第2天高兴：概率 $0.5 \times 0.5 = 0.25$，失落 0 次
3. 第1天高兴，第2天不高兴：概率 $0.5 \times 0.5 = 0.25$，失落 1 次
4. 第1天高兴，第2天高兴：概率 $0.5 \times 0.5 = 0.25$，失落 0 次

期望：

$$E = 0.25 \times 0 + 0.25 \times 0 + 0.25 \times 1 + 0.25 \times 0 = 0.25 $$

---

五、算法正确性分析

5.1 边界策略的正确性

第 1 天选最小概率：

• 初始不高兴，第 1 天无失落
• 选最小概率让她最可能高兴，为后续减少失落

第 $k$ 天选最大概率：

• 最后一天后没有失落
• "浪费"一个高概率项目，不影响总期望

---

5.2 贪心策略的有效性

虽然严格证明复杂，但直觉上：

• 当两端状态都"坏"时（$\text{nowl} + \text{nowr} \geq 1$），选择更坏的
• 当至少有一端状态"好"时，选择更好的
• 这符合期望最小化的目标

---

六、复杂度总结

时间复杂度

• 排序：$O(n \log n)$
• 主循环：$O(\min(k, n))$（批量优化后）
• 总复杂度：$O(n \log n)$

空间复杂度

• $O(n)$（存储项目信息）

---

七、易错点与注意事项

7.1 易错点 1：精度问题

问题：概率计算涉及除法，需要高精度。

// ✅ 正确
a[i].first = 1.0 * x / y;  // long double

// ❌ 错误
a[i].first = x / y;  // 整数除法

---

7.2 易错点 2：边界条件

$k = 1$ 的特判：

• 必须特判，否则 $k-2 = -1$ 会出错

项目用完的处理：

while (!a[l].second) l++;
while (!a[r].second) r--;

必须在每次循环开始时检查。

---

7.3 易错点 3：公式对称性

左端和右端的期望公式略有不同：

• 左端：(1 - nowl) * a[l].first
• 右端：(1 - a[r].first) * nowr

这不是错误，而是算法的巧妙设计！

---

八、知识点总结

核心算法技巧

1. ✅ 概率期望计算

   • 失落期望 = P(昨天高兴) × P(今天不高兴)
   • 连续使用项目的期望累加

2. ✅ 贪心策略

   • 边界优化（第1天和第k天）
   • 中间贪心选择

3. ✅ 双指针

   • 左右两端维护不同概率的项目
   • 动态决策

4. ✅ 批量处理优化

   • 相同概率项目一次性处理
   • 减少循环次数

---

适用场景

• ✅ 概率期望问题
• ✅ 序列安排优化
• ✅ 贪心策略设计
• ✅ 状态转移

---

九、总结

算法精髓

本题采用的双端贪心 + 概率期望算法的核心思想：

1. 边界优化：第1天和第k天特殊处理
2. 贪心策略：根据当前状态动态选择
3. 批量优化：相同概率项目一次性处理
4. 期望计算：精确的数学公式