---

1518. 换水问题

• 标签：数学、模拟
• 难度：简单

题目链接

• 1518. 换水问题 - 力扣

题目大意

描述：初始有 $numBottles$ 瓶水。每 $numExchange$ 个空瓶可以换 $1$ 瓶新水。

要求：返回最多能喝多少瓶水。

说明：

• $1 \le numBottles \le 100$。
• $2 \le numExchange \le 100$。

示例：

• 示例 1：

输入：numBottles = 9, numExchange = 3
输出：13
解释：你可以用 3 个空瓶兑换 1 瓶水。
所以最多能喝到 9 + 3 + 1 = 13 瓶水。

• 示例 2：

输入：numBottles = 15, numExchange = 4
输出：19
解释：你可以用 4 个空瓶兑换 1 瓶水。
所以最多能喝到 15 + 3 + 1 = 19 瓶水。

解题思路

思路 1：模拟

1. 核心思想

模拟喝水、换空瓶的过程。初始 $total = numBottles$（已喝的数量），$empty = numBottles$（空瓶数）。

当 $empty \ge numExchange$ 时：

• 能换的新水瓶数 $new = empty // numExchange$。
• $total += new$。
• $empty = empty \% numExchange + new$。

2. 具体步骤

第 1 步：$total = empty = numBottles$。

第 2 步：当 $empty \ge numExchange$，重复上述过程。

第 3 步：返回 $total$。

3. 举例说明

以 $numBottles = 15, numExchange = 4$ 为例：

• 喝 $15$，空瓶 $15$，换 $15//4=3$，剩 $15\%4=3$ 空瓶。
• 再喝 $3$，$total=18$，空瓶 $3+3=6$，换 $6//4=1$，剩 $6\%4=2$。
• 再喝 $1$，$total=19$，空瓶 $2+1=3$，不够换。

总共 $19$ 瓶。

以 $numBottles = 5, numExchange = 5$ 为例：

• 喝 $5$，空瓶 $5$，换 $1$。
• 再喝 $1$，$total=6$，空瓶 $1$，不够换。

总共 $6$ 瓶。

思路 1：代码

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        total = empty = numBottles
        while empty >= numExchange:
            new = empty // numExchange
            total += new
            empty = empty % numExchange + new
        return total

思路 1：复杂度分析

• 时间复杂度：$O(\log_{numExchange} numBottles)$。
• 空间复杂度：$O(1)$。