🔗 🟢 1518. Water Bottles 1245

tags: `Weekly Contest 198` `模擬(Simulation)` `數學(Math)`

題意

你有 $numBottles$ 罐全新未拆封的礦泉水，你可以用 $numExchange$ 個空瓶子兌換一瓶新的礦泉水。

你可以喝掉礦泉水瓶子中的水，每喝掉一瓶水，瓶子就會變成空的。

給定兩個整數 $numBottles$ 和 $numExchange$ ，請你計算你最多可以喝到多少瓶礦泉水。

思路

方法一：模擬(Simulation)

模擬整個過程，從最初的 $numBottles$ 開始，持續地將空瓶兌換成新的礦泉水，直到空瓶數不夠兌換新的礦泉水為止。

初始化 $ans$ 為 $numBottles$ ，表示把一開始的礦泉水全部喝完，使其成為空瓶。接下來，當 $numBottles$ 大於等於 $numExchange$ 時：

計算可以兌換的新瓶子數量 $q$ 和剩餘的空瓶數量 $r$ 。
將 $q$ 加到 $ans$ 中，表示多喝了 $q$ 瓶水。
更新 $numBottles$ 為 $q + r$ ，繼續下一輪兌換。

持續上述過程直到無法再進行兌換操作為止。最後返回 $ans$ 。

複雜度分析

時間複雜度: $\mathcal{O}(\log_{e}{n})$ $O (lo g_{e} n)$ ，其中 $n$ $n$ 是 $numBottles$ $n u m B o ttl es$ 、 $e$ $e$ 是 $numExchange$ $n u m E x c han g e$ 。
- 每次迭代時，瓶子的數量大致上會除以 $numExchange$ ，因此迭代次數是對數級別的。
空間複雜度: $\mathcal{O}(1)$ 。

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        ans = numBottles
        while numBottles >= numExchange:
            q, r = divmod(numBottles, numExchange)
            numBottles = q + r
            ans += q
        return ans

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int ans = numBottles;
        while (numBottles >= numExchange) {
            ans += numBottles / numExchange;
            numBottles = numBottles / numExchange + numBottles % numExchange;
        }
        return ans;
    }
};

方法二：數學(Math)

為方便表示，令 $n = numBottles$ 、 $e = numExchange$ 。

若將空瓶子視為可消耗的資源，則每次兌換全新礦泉水時，實際上會消耗 $e - 1$ 個空瓶子。因此，我們可以將整個過程視為一個循環，每次循環消耗 $e - 1$ 個空瓶子，直到剩下的空瓶子不足以兌換新的礦泉水為止。

故可以求得兌換礦泉水的次數為 $k = \left\lfloor \frac{n}{e - 1} \right\rfloor$ ，即可以喝到的礦泉水數量為 $n + k$ 。但是需要注意，若 $n$ 為 $e - 1$ 的倍數時，無法進行最後一次兌換，因此需要特別處理。這裡使用了 $\left\lfloor \frac{n - 1}{e - 1} \right\rfloor$ 來計算 $k$ ，避免了這個問題。

複雜度分析

時間複雜度: $\mathcal{O}(1)$ 。
空間複雜度: $\mathcal{O}(1)$ 。

1
2
3

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        return numBottles + (numBottles - 1) // (numExchange - 1)

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        return numBottles + (numBottles - 1) / (numExchange - 1);
    }
};