空瓶换汽水问题C++解法及公式推导

好的，我们来解决这个经典的“空瓶换汽水”问题。 ## 🧩 问题分析 小丽有 **n** 瓶汽水，每喝完一瓶得到一个空瓶，**k** 个空瓶可以换一瓶新的汽水（换来的汽水喝完后又产生空瓶）。问：小丽 **最终能喝多少瓶**？ **核心思路**： - 初始有 `n` 瓶，**已喝** = `n`，**空瓶数** = `n`。 - 只要空瓶数 ≥ `k`，就不断用空瓶换汽水喝： - 换得的汽水瓶数 = `空瓶数 / k`（整数除法）。 - 喝完这些汽水，**已喝**增加，**空瓶数**更新为：`(空瓶数 % k) + 新换得的瓶数`。 - 重复直到空瓶数 < `k`。 ### ⚡ 优化提示 当 `n` 和 `k` 很大（≤1e8）时，直接模拟可能会超时（虽然本例模拟复杂度为 O(logₖ n)，很安全），但我们可以用公式直接计算，效率更高。 **公式推导**： - 每换一瓶，实际消耗的空瓶数是 `k-1`（因为换来的那瓶喝完又产生1个空瓶“还”回去了）。 - 一开始有 `n` 个空瓶，相当于用这些空瓶去“换”汽水，直到剩下空瓶数不足 `k`。 - 总空瓶数可“支持”的兑换次数为：`(n-1) / (k-1)`（因为最后会剩下至少1个空瓶）。 - 最终喝到的汽水 = 初始喝的 `n` + 兑换的 `(n-1) / (k-1)`。 这个公式在 `k` 很大时要注意边界情况。更通用的办法是直接用**循环模拟**，因为最大循环次数约 `logₖ n`，对 1e8 来说最多几十次，非常快。 --- ## 🔧 C++ 代码实现（模拟法，清晰直观） ```cpp #include <iostream> using namespace std; int main() { long long n, k; // 使用long long防止溢出 while (cin >> n >> k) { long long total = n; // 初始已经喝掉 n 瓶 long long empty = n; // 当前空瓶数 while (empty >= k) { long long newBottles = empty / k; // 这次用空瓶换来的汽水 total += newBottles; // 喝掉它们 empty = empty % k + newBottles; // 新空瓶 = 上次剩下的 + 这次喝完的 } cout << total << endl; } return 0; } ``` ### 📝 代码解释 1. **`long long`**：因为 `n` 和 `k` 最大 1e8，但运算过程中 `total` 可能超过 `int` 范围（如 n=1e8, k=2 时，结果 ≈ 2e8-1），所以用 `long long` 安全。 2. **`while (empty >= k)`**：只要空瓶够换，就继续。 3. **`newBottles = empty / k`**：整数除法，得到本次能换几瓶。 4. **`empty = empty % k + newBottles`**： - `empty % k`：换完之后剩下的空瓶（不足 k 个）。 - `+ newBottles`：换来的新汽水喝完又变成空瓶。 5. **输入**：题目说“每组测试数据一行”，所以用 `while (cin >> n >> k)` 循环读入直到文件结束。 --- ## 🚀 进阶：数学公式法（效率更高，但需注意边界） ```cpp #include <iostream> using namespace std; int main() { long long n, k; while (cin >> n >> k) { long long total = n + (n - 1) / (k - 1); cout << total << endl; } return 0; } ``` **公式说明**： - `(n-1) / (k-1)` 是额外能换得的汽水瓶数。 - 为什么减1？因为最后至少会剩下1个空瓶无法再换。 - ⚠️ **注意**：当 `k = 2` 时 `(n-1)/(1) = n-1`，结果 = `2n-1`，符合我们手动模拟的结果（如 n=3,k=2 → 5瓶）。 - 该公式在所有 `k>1` 时都成立。 --- ## 📌 开发建议 1. **注意数据类型**：类似问题中，结果可能远大于输入，**务必用 `long long`**，避免溢出。 2. **边界测试**： - n=1, k=2 → 1（不够换） - n=5, k=2 → 9 - n=100000000, k=2 → 199999999（接近 2e8，int 会溢出） 3. **代码可读性**：即使公式简单，也建议加上注释，说明推导逻辑，方便日后维护。 4. **性能**：本题中模拟法已经足够快（O(logₖ n)）。但如果你需要处理海量查询（Q 很大），建议预先推导公式，避免每次循环。 --- ## 💡 常见陷阱 - **忽略初始空瓶**：有些人会忘记最开始喝的 n 瓶也算入总数。 - **忘记更新空瓶**：换来的新汽水喝完又产生空瓶，必须加到 `empty` 里。 - **整数除法理解**：C++ 中整数除法自动向下取整，符合题意。 --- ######[AI写代码神器 | 1323点数解答 | 2026-05-23 15:14:01]