蓄水

难度: Easy

给定 N 个无限容量且初始均空的水缸，每个水缸配有一个水桶用来打水，第 `i` 个水缸配备的水桶容量记作 `bucket[i]`。小扣有以下两种操作： - 升级水桶：选择任意一个水桶，使其容量增加为 `bucket[i]+1` - 蓄水：将全部水桶接满水，倒入各自对应的水缸每个水缸对应最低蓄水量记作 `vat[i]`，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。注意：实际蓄水量 **达到或超过** 最低蓄水量，即完成蓄水要求。 **示例 1：** >输入：`bucket = [1,3], vat = [6,8]` > >输出：`4` > >解释： >第 1 次操作升级 bucket[0]； >第 2 ~ 4 次操作均选择蓄水，即可完成蓄水要求。 ![vat1.gif](https://pic.leetcode-cn.com/1616122992-RkDxoL-vat1.gif) **示例 2：** >输入：`bucket = [9,0,1], vat = [0,2,2]` > >输出：`3` > >解释： >第 1 次操作均选择升级 bucket[1] >第 2~3 次操作选择蓄水，即可完成蓄水要求。 **提示：** - `1 <= bucket.length == vat.length <= 100` - `0 <= bucket[i], vat[i] <= 10^4`

Submission

运行时间: 23 ms

内存: 16.2 MB

class Solution:
    def storeWater(self, bucket: List[int], vat: List[int]) -> int:
        n = len(bucket)
        pq = []
        cnt = 0
        for i in range(n):
            if bucket[i] == 0 and vat[i]:
                cnt += 1
                bucket[i] += 1
            if vat[i] > 0:
                heapq.heappush(pq, [-math.ceil(vat[i]/bucket[i]), i])
        if not pq:
            return 0
        res = float('inf')
        while cnt < res:
            v, i = heapq.heappop(pq)
            v = -v
            res = min(res, cnt + v)
            if v == 1:
                break
            t = (vat[i] + v - 2) // (v - 1)
            cnt += t - bucket[i]
            bucket[i] = t
            heapq.heappush(pq, [-math.ceil(vat[i]/bucket[i]), i])
        return res

Explain

该题解采用了贪心算法和优先队列（最大堆）来解决问题。首先，对每个水缸进行初始化，如果水桶初始容量为0但水缸需要水，则强制升级该水桶一次。同时，计算每个水缸的最初需要的蓄水操作次数（向上取整除），并将其以负数形式存入最大堆（以保持堆为最大堆）。接着，算法执行循环，每次从堆中取出需要水量最大的水缸，并尝试通过增加水桶容量来减少蓄水所需的总操作次数。每次计算当前可能的最小操作次数并更新结果。如果最小次数不再改善，则停止循环。

时间复杂度: O(n log n)

空间复杂度: O(n)

# Definition of Solution class

class Solution:
    def storeWater(self, bucket: List[int], vat: List[int]) -> int:
        n = len(bucket)
        pq = []  # This is the max-heap
        cnt = 0  # Count of initial operations needed
        for i in range(n):
            # Initial adjustments if bucket is zero but water is needed
            if bucket[i] == 0 and vat[i]:
                cnt += 1
                bucket[i] += 1
            # Only consider vats that need water
            if vat[i] > 0:
                heapq.heappush(pq, [-math.ceil(vat[i]/bucket[i]), i])
        # If there are no operations needed, return 0
        if not pq:
            return 0
        res = float('inf')  # Initialize result to infinite
        # Main loop to determine minimum operations
        while cnt < res:
            v, i = heapq.heappop(pq)
            v = -v
            res = min(res, cnt + v)
            # If only one pour is needed, break
            if v == 1:
                break
            # Calculate the next state of the bucket
            t = (vat[i] + v - 2) // (v - 1)
            cnt += t - bucket[i]
            bucket[i] = t
            # Push new state to the heap
            heapq.heappush(pq, [-math.ceil(vat[i]/bucket[i]), i])
        return res

Explore

在初始检查中，如果水桶的容量为0且相应的水缸需要水，那么该水桶无法进行任何蓄水操作，因此必须至少升级一次以使其具备基本的蓄水功能。若不升级，该水桶将无法参与蓄水过程，无法满足任何水量需求。在其他情况下，即使水桶的初始容量不为0，进行初始升级可能会减少所需的总操作次数，但这需要具体分析每个水桶和水缸的容量比。算法通过动态地在迭代过程中调整每个水桶的容量来优化操作次数，而非一开始就盲目升级，这样可以更灵活地适应不同的需求情况。

Python的`heapq`库默认实现的是最小堆，而本题解需要使用最大堆来保证每次都能处理需要水量最大的水缸。通过将元素的负数形式存储在堆中，可以利用最小堆的性质反向模拟最大堆的功能。这样设计的好处是可以直接使用Python标准库而不需要自定义数据结构，同时简化了代码实现，提高了效率和可读性。

算法会在两种情况下停止循环：1) 当当前的最小操作次数不再改善，即已找到可能的最小操作数时；2) 当从堆中取出的元素表明只需进行一次蓄水操作即可满足需求时，即`v == 1`。这是因为如果某个水缸在经过一次操作后就可以被完全填满，则进一步尝试减少操作次数已无意义。循环的主要终止条件是基于当前操作次数与已知的最小操作次数比较，如果当前状态下的操作次数已经不可能比已知的最小操作次数更小，那么继续循环将不会有任何改善，从而结束循环。