题目分析

问题本质

对于 $n$ 个食物，每个食物有两种操作：乘以 $a_i$ 或加上 $b_i$，从体重 $1$ 开始，求通过最优顺序和操作选择能达到的最大体重。

关键观察

操作性质分析

• 乘法操作：$x \to x \times a_i$，效果取决于当前值 $x$
• 加法操作：$x \to x + b_i$，效果相对固定
• 操作顺序和选择策略相互影响

重要分类讨论

情况1：$a_i = 1$

• 乘法无效：$x \times 1 = x$
• 总是选择加法操作

情况2：$a_i > 1$ 需要比较乘法和加法的相对收益：

• 如果当前值 $x$ 很小，加法可能更优
• 如果当前值 $x$ 很大，乘法可能更优

算法框架

解法：贪心排序 + 操作分离

核心洞察： 通过分析可以发现最优策略具有以下结构：

1. 先进行所有加法操作
2. 后进行所有乘法操作
3. 在各自组内按特定顺序排列

证明思路：

• 加法操作的效果是加常数，在值较小时进行收益更大
• 乘法操作的效果是缩放，在值较大时进行能放大之前的收益

具体贪心策略

步骤1：分类处理

• 对于 $a_i = 1$ 的食物：直接选择加法，按 $b_i$ 降序排列
• 对于 $a_i > 1$ 的食物：需要进一步分析

步骤2：$a_i > 1$ 的食物排序 对于两个食物 $i$ 和 $j$，比较它们的相对顺序：

• 如果先 $i$ 后 $j$：效果为 $(x + b_i) \times a_j + b_j$
• 如果先 $j$ 后 $i$：效果为 $(x + b_j) \times a_i + b_i$

比较两者大小，得到排序依据：按 $\frac{b_i}{a_i-1}$ 或类似指标排序

步骤3：最终操作顺序

1. 所有 $a_i = 1$ 的食物（按 $b_i$ 降序）
2. 所有 $a_i > 1$ 的食物（按特定指标排序）

算法细节

排序指标推导

对于两个食物 $i$ 和 $j$，比较：

$$(x + b_i)a_j + b_j \ \text{vs} \ (x + b_j)a_i + b_i $$

整理得比较：

$$b_i(a_j - 1) \ \text{vs} \ b_j(a_i - 1)$$

因此排序指标为：按 $\frac{b_i}{a_i-1}$ 升序排列

特殊情况处理

$a_i = 1$ 的情况：

• 直接选择加法操作
• 在加法组内按 $b_i$ 降序排列（因为先加大的数收益更大）

$a_i \geq b_i$ 的情况（特殊性质B）：

• 通常乘法操作更优
• 但仍需考虑与其他食物的相对顺序

模运算处理

• 最终答案对 $10^9+7$ 取模
• 但注意：题目要求先最大化实际体重，再取模
• 不能直接在模意义下比较大小

复杂度分析

时间复杂度

• 排序：$O(n \log n)$
• 模拟操作：$O(n)$
• 总复杂度：$O(n \log n)$

空间复杂度

• 存储食物参数：$O(n)$
• 排序临时数组：$O(n)$

实现考虑

大数处理

• 由于 $a_i, b_i \leq 10^6$，$n \leq 5\times 10^5$
• 中间结果可能非常大，需要使用高精度或对数比较

比较策略

由于实际值可能很大，直接计算比较可能溢出，可以采用：

1. 对数比较：比较 $\log(\text{方案1})$ 和 $\log(\text{方案2})$
2. 分数比较：避免大数乘法

特殊性质优化

性质A（$a_i = 1$）：

• 所有食物都选择加法
• 按 $b_i$ 降序排列即可

性质B（$a_i \geq b_i$）：

• 通常选择乘法操作更优
• 但仍需考虑操作顺序

性质D（$a_i \geq 2$）：

• 简化了排序指标的计算

正确性验证

小数据验证

对于样例1：

• 食物参数：$(1,100), (2,200), (3,300), (4,400), (5,500)$
• 最优策略：先加100,200，再乘3,4,5
• 结果：$((1+100+200) \times 3 \times 4 \times 5) = 18060$

边界情况

• 所有 $a_i = 1$：纯加法问题
• 所有 $a_i > 1$：纯乘法问题（但 $b_i$ 不为0）
• 混合情况：需要仔细排序

总结

本题的核心在于发现加法操作应该先于乘法操作的贪心性质，以及在各自组内找到最优的排序策略。通过数学推导得到排序指标 $\frac{b_i}{a_i-1}$，从而在 $O(n \log n)$ 时间内解决问题。关键难点在于理解不同操作之间的相互影响，以及如何在不直接计算大数的情况下比较不同策略的优劣。