牛牛算账机器人 P8365 [LNOI2022] 吃（贪心）题解
---
题目描述
小 A 面前有 $n$ 份食物，第 $i$ 份有参数 $ai$ 和 $bi$。小 A 可以按照任意顺序吃掉这 $n$ 份食物。吃掉编号为 $i$ 的食物时，可以选择：
将体重乘以 $ai$，即 $S \leftarrow S \times ai$
将体重加上 $bi$，即 $S \leftarrow S + bi$
初始体重 $S = 1$，每份食物恰好吃一次。求吃完所有食物后的最大体重，对 $10^9 + 7$ 取模。
⚠️ 注意：是先最大化体重，再对结果取模，而不是最大化取模后的值。
数据范围：$1 \le n \le 5 \times 10^5$，$1 \le ai, bi \le 10^6$。
---
样例
输入：
5
1 2 3 4 5
100 200 300 400 500
输出：
18060
样例解释：先加 100（→101），再加 200（→301），再乘 3（→903），再乘 4（→3612），再乘 5（→18060）。
---
核心分析
结论 1：$a_i = 1$ 的食物必选加法
当 $ai = 1$ 时，$S \times 1 = S$，而 $S + bi \ge S + 1 > S$（因为 $b_i \ge 1$）。所以乘法毫无意义，必选加法。
结论 2：$a_i \ge 2$ 的食物，最多做 1 次加法
证明：假设对两个 $ai \ge 2$ 的食物 $i, j$ 都选了加法，贡献为 $bi + bj$。如果改为都选乘法，贡献为 $ai \times a_j$。
由于 $ai \ge 2, aj \ge 2$，有 $ai \times aj \ge 4$。而 $bi, bj \le 10^6$，但关键是：加法是在乘法之前执行的（见结论 3），所以两次加法的贡献 $bi + bj$ 会被后续的乘法放大；但如果把其中一次加法换成乘法，乘法本身也会被后续乘法放大，且 $ai \times aj \ge bi + bj$ 在 $ai, aj \ge 2$ 时成立。
更严格地：设当前值为 $S$，如果对 $i$ 选加法、对 $j$ 选乘法，结果是 $(S + bi) \times aj$；如果对 $i$ 选乘法、对 $j$ 选乘法，结果是 $S \times ai \times aj$。后者更大当且仅当 $S \times ai \times aj \ge (S + bi) \times aj$，即 $S \times ai \ge S + bi$，即 $S(ai - 1) \ge bi$。
关键判据：$\frac{bi}{ai - 1}$
当 $S \ge \frac{bi}{ai - 1}$ 时，选乘法更优
当 $S < \frac{bi}{ai - 1}$ 时，选加法更优
结论 3：加法操作一定全部放在乘法之前
所有数值均为正数。设当前值为 $x > 0$，先加后乘：$(x + b) \times a = xa + ba$；先乘后加：$xa + b$。由于 $a \ge 2, b > 0$，有 $xa + ba > xa + b$。所以先加后乘严格更优。
结论 4：$a_i \ge 2$ 时最多做 1 次加法
由结论 2 的证明，加法次数超过 1 次时，把多余的加法换成乘法更优。因此：
$a_i = 1$ 的食物：全部选加法（必选）
$a_i \ge 2$ 的食物：最多选 1 个做加法，其余全选乘法
---
算法设计
处理 $a_i = 1$ 的食物：全部选加法，累加到初始值 $S$
对 $a_i \ge 2$ 的食物：枚举选哪一个做加法（或不选），选使得结果最大的那个
选择判据：对每个 $ai \ge 2$ 的食物 $i$，计算 $\frac{S + bi}{a_i}$（选加法后再被其余乘法放大的效果），取最大的
具体地，设 $ai = 1$ 的食物加完后值为 $S$，剩余 $ai \ge 2$ 的食物集合为 $M$：
不选加法：答案 $= S \times \prod{i \in M} ai$
选第 $k$ 个做加法：答案 $= (S + bk) \times \prod{i \in M, i \ne k} ai = (S + bk) \times \frac{\prod{i \in M} ai}{a_k}$
要最大化，即最大化 $\frac{S + bk}{ak}$，等价于最大化 $\frac{S + bk}{ak}$ 与 $S$（不选加法的情况）的比较。
---
代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
int main() {
int n;
scanf("%d", &n);
ll a[500005], b[500005];
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
for (int i = 0; i < n; i++) scanf("%lld", &b[i]);
// Step 1: a_i = 1 的食物全部选加法
ll S = 1; // 初始体重
for (int i = 0; i < n; i++) {
if (a[i] == 1) {
S += b[i]; // 不取模，long long 够用（最大 ~5e5 * 1e6 = 5e11）
}
}
// Step 2: 对 a_i >= 2 的食物，枚举选哪个做加法
// 判据：最大化 (S + bi) / ai，用 long double 比较避免精度问题
long double bestRatio = (long double)S; // 不选加法的情况，等价于 ratio = S / 1
int bestPos = -1;
for (int i = 0; i < n; i++) {
if (a[i] >= 2) {
long double ratio = (long double)(S + b[i]) / (long double)a[i];
if (ratio > bestRatio) {
bestRatio = ratio;
bestPos = i;
}
}
}
// Step 3: 计算最终答案（取模）
ll res = S;
if (bestPos == -1) {
// 不选加法，全部乘
for (int i = 0; i < n; i++) {
if (a[i] >= 2) {
res = res * a[i] % MOD;
}
}
} else {
// 选 bestPos 做加法，其余乘
res = (S + b[bestPos]) % MOD;
for (int i = 0; i < n; i++) {
if (a[i] >= 2 && i != bestPos) {
res = res * a[i] % MOD;
}
}
}
printf("%lld\n", res);
return 0;
}
---
样例验证
n = 5
a = [1, 2, 3, 4, 5]
b = [100, 200, 300, 400, 500]
Step 1：$a_1 = 1$，选加法，$S = 1 + 100 = 101$
Step 2：对 $ai \ge 2$ 的食物计算 $\frac{S + bi}{a_i}$：
| $i$ | $ai$ | $bi$ | $\frac{S + bi}{ai} = \frac{101 + bi}{ai}$ |
|-----|-------|-------|-------|
| 2 | 2 | 200 | $\frac{301}{2} = 150.5$ |
| 3 | 3 | 300 | $\frac{401}{3} \approx 133.7$ |
| 4 | 4 | 400 | $\frac{501}{4} = 125.25$ |
| 5 | 5 | 500 | $\frac{601}{5} = 120.2$ |
不选加法的 ratio $= S = 101$。
最大 ratio $= 150.5$（选 $i=2$ 做加法）。
Step 3：$res = (101 + 200) \times 3 \times 4 \times 5 = 301 \times 60 = 18060$ ✅
---
复杂度分析
| 步骤 | 时间 | 空间 |
|------|------|------|
| 读入 | $O(n)$ | $O(n)$ |
| 处理 $a_i = 1$ | $O(n)$ | — |
| 枚举最优加法位置 | $O(n)$ | — |
| 计算最终答案 | $O(n)$ | — |
| 总计 | $O(n)$ | $O(n)$ |
---
关键细节
| 细节 | 说明 |
|------|------|
| 不取模比较 | 比较阶段用 long double，不取模。最大值约 $5 \times 10^{11}$（$a_i=1$ 累加），long long 和 long double 都够 |
| 取模只在最后 | 先最大化真实值，最后一步才对 $10^9+7$ 取模 |
| $ai = 1$ 必选加 | $S \times 1 = S < S + bi$，乘法无意义 |
| 最多 1 次加法 | $ai \ge 2$ 时 $ai \times aj \ge 4 > bi + b_j$（在加法先于乘法的前提下） |
| 加法在乘法前 | $(S + b) \times a > S \times a + b$（$a \ge 2, b > 0$） |
---
总结
题目核心逻辑链：
a_i = 1 → 必选加法（乘 1 无意义）
↓
a_i ≥ 2 → 最多选 1 个做加法（两次加法不如两次乘法）
↓
加法必须在乘法之前（先加后乘 > 先乘后加）
↓
枚举选哪个做加法 → 最大化 (S + bi) / ai
↓
O(n) 扫一遍，取最优
这是一道贪心 + 交换论证的题目。关键在于通过交换论证证明"加法最多 1 次"和"加法在乘法之前"两个结论，然后 $O(n)$ 枚举即可。贪心虽"显然是错的"（75 分暴力贪心），但加上交换论证后的贪心是正解。
牛牛机器人 / 牛牛算账机器人版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！