1 題目

Alice 和 Bob 打算給花園里的 n 株植物澆水。植物排成一行，從左到右進行標記，編號從 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。

每一株植物都需要澆特定量的水。Alice 和 Bob 每人有一個水罐，最初是滿的 。他們按下面描述的方式完成澆水：

• Alice 按 從左到右 的順序給植物澆水，從植物 0 開始。Bob 按 從右到左 的順序給植物澆水，從植物 n - 1 開始。他們 同時 給植物澆水。
• 無論需要多少水，為每株植物澆水所需的時間都是相同的。
• 如果 Alice/Bob 水罐中的水足以 完全 灌溉植物，他們 必須 給植物澆水。否則，他們 首先（立即）重新裝滿罐子，然后給植物澆水。
• 如果 Alice 和 Bob 到達同一株植物，那么當前水罐中水 更多 的人會給這株植物澆水。如果他倆水量相同，那么 Alice 會給這株植物澆水。

給你一個下標從 0 開始的整數數組 plants ，數組由 n 個整數組成。其中，plants[i] 為第 i 株植物需要的水量。另有兩個整數 capacityA 和 capacityB 分別表示 Alice 和 Bob 水罐的容量。返回兩人澆灌所有植物過程中重新灌滿水罐的 次數 。

示例 1：

輸入：plants = [2,2,3,3], capacityA = 5, capacityB = 5
輸出：1
解釋：
- 最初，Alice 和 Bob 的水罐中各有 5 單元水。
- Alice 給植物 0 澆水，Bob 給植物 3 澆水。
- Alice 和 Bob 現在分別剩下 3 單元和 2 單元水。
- Alice 有足夠的水給植物 1 ，所以她直接澆水。Bob 的水不夠給植物 2 ，所以他先重新裝滿水，再澆水。
所以，兩人澆灌所有植物過程中重新灌滿水罐的次數 = 0 + 0 + 1 + 0 = 1 。

示例 2：

輸入：plants = [2,2,3,3], capacityA = 3, capacityB = 4
輸出：2
解釋：
- 最初，Alice 的水罐中有 3 單元水，Bob 的水罐中有 4 單元水。
- Alice 給植物 0 澆水，Bob 給植物 3 澆水。
- Alice 和 Bob 現在都只有 1 單元水，并分別需要給植物 1 和植物 2 澆水。
- 由于他們的水量均不足以澆水，所以他們重新灌滿水罐再進行澆水。
所以，兩人澆灌所有植物過程中重新灌滿水罐的次數 = 0 + 1 + 1 + 0 = 2 。

示例 3：

輸入：plants = [5], capacityA = 10, capacityB = 8
輸出：0
解釋：
- 只有一株植物
- Alice 的水罐有 10 單元水，Bob 的水罐有 8 單元水。因此 Alice 的水罐中水更多，她會給這株植物澆水。
所以，兩人澆灌所有植物過程中重新灌滿水罐的次數 = 0 。

提示：

• n == plants.length
• 1 <= n <= 105
• 1 <= plants[i] <= 106
• max(plants[i]) <= capacityA, capacityB <= 109

2 解答

class Solution:
    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
        n = len(plants)
        a = 0
        b = n-1
        retain_a = capacityA
        retain_b = capacityB
        ans = 0

        while a<b:
            if retain_a < plants[a]:
                retain_a = capacityA
                ans = ans + 1
            retain_a -= plants[a]
            a += 1

            if retain_b < plants[b]:
                retain_b =  capacityB
                ans += 1
            retain_b -= plants[b]
            b -= 1

        if a==b and max(retain_b , retain_a)<plants[a]:
            ans += 1

        return ans