2105-给植物浇水 II

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

方法一：模拟

思路与算法

我们可以模拟 Alice 与 Bob 浇水的过程，并在模拟的过程中统计重新灌满水罐的次数。

我们用 pos}_a, \textit{pos}_b 分别表示 Alice 与 Bob 当前所在植物的下标，并用 val}_a, \textit{val}_b 分别表示两人水罐中的剩余水量。我们用 n 表示植物的数量，当模拟开始时，Alice 与 Bob 的位置满足 pos}_a = 0, \textit{pos}_b = n - 1；剩余水量满足 val}_a = \textit{capacity}_a, \textit{val}_b = \textit{capacity}_b。

当 Alice 与 Bob 相遇前的每一个时刻，我们需要模拟两人对当前位置植物浇水的过程。以 Alice 为例，我们比较当前剩余水量 val}_a 与植物所需水量 plants}[\textit{pos}_a] 的大小，此时会有两种情况：

• 如果剩余水量大于等于植物所需水量，即 val}_a \ge \textit{plants}[\textit{pos}_a]，此时不需要重新灌满水罐，浇水后剩余水量变为 val}_a - \textit{plants}[\textit{pos}_a]；

• 如果剩余水量小于等于植物所需水量，即 val}_a < \textit{plants}[\textit{pos}_a]，此时需要先重新灌满水罐，我们需要将重新灌满水罐的次数加上 1，浇水后剩余水量等于水罐容积减去植物所需水量，即 capacity}_a - \textit{plants}[\textit{pos}_a]。

在浇水操作后，我们需要将 Alice 与 Bob 分别移动至下一株植物的位置，即 pos}_a 变为 pos}_a + 1， pos}_b 变为 pos}_b - 1。

当 Alice 与 Bob 相遇后，此时根据 n 的奇偶性会有两种情况：

• n 为偶数，相遇后两人所在位置都被浇过水，因此无需任何操作；

• n 为奇数，两人位置重合，且该位置植物未被浇水，此时需要先比较两人的剩余水量，再进行上文的浇水操作并维护重新灌满次数：如果 val}_a \ge \textit{val}_b，则 Alice 浇水，反之则 Bob 浇水。

事实上，对于可能的最后一步操作，我们只需要判断是否需要重新灌满水罐并维护对应次数即可。

模拟结束后，我们返回统计的重新灌满水罐次数作为答案。

代码

[sol1-C++]

class Solution {
public:
    int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
        int res = 0;   // 灌满水罐次数
        int n = plants.size();   // 两人位置
        int posa = 0, posb = n - 1;   // 两人剩余水量
        int vala = capacityA, valb = capacityB;
        // 模拟相遇前的浇水过程
        while (posa < posb) {
            if (vala < plants[posa]) {
                ++res;
                vala = capacityA - plants[posa];
            }
            else {
                vala -= plants[posa];
            }
            ++posa;
            if (valb < plants[posb]) {
                ++res;
                valb = capacityB - plants[posb];
            }
            else {
                valb -= plants[posb];
            }
            --posb;
        }
        // 模拟相遇后可能的浇水过程
        if (posa == posb) {
            if (vala >= valb && vala < plants[posa]) {
                ++res;
            }
            if (vala < valb && valb < plants[posb]) {
                ++res;
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
        res = 0   # 灌满水罐次数
        n = len(plants)
        posa, posb = 0, n - 1   # 两人位置
        vala, valb = capacityA, capacityB   # 两人剩余水量
        # 模拟相遇前的浇水过程
        while posa < posb:
            if vala < plants[posa]:
                res += 1
                vala = capacityA - plants[posa]
            else:
                vala -= plants[posa]
            posa += 1
            if valb < plants[posb]:
                res += 1
                valb = capacityB - plants[posb]
            else:
                valb -= plants[posb]
            posb -= 1
        # 模拟相遇后可能的浇水过程
        if posa == posb:
            if vala >= valb and vala < plants[posa]:
                res += 1
            elif vala < valb and valb < plants[posb]:
                res += 1
        return res

复杂度分析

• 时间复杂度：O(n)，其中 n 为 plants 的长度。模拟浇水过程并统计重新灌满水罐次数的时间复杂度为 O(n)。

• 空间复杂度：O(1)。