LCP 33-蓄水

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

给定 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

方法一：贪心 + 数学

思路与算法

题目给出 n 个无限容量且初始均空的水缸，每个水缸配有一个对应的水桶用来打水，其中第 i 个水缸配备的水桶容量为 bucket}[i]，对应的最低蓄水量为 vat}[i]。现在我们有以下两种操作：

  • 「升级水桶」：选择任意一个水桶，使其容量加一。
  • 「蓄水」：将全部水桶接满水，倒入各自对应的水缸。

现在我们需要返回能使全部水缸完成蓄水要求的最少操作次数。首先显然应该把所有「升级水桶」的操作放在「蓄水」之前，这样每次蓄水时的增益是最大的。那么若当前已知最终需要「蓄水」次数为 k，则对于第 i 个水缸配备的水桶在「蓄水」操作前的容量 m_i 至少应该达到

m_i = \lceil{\textit{vat}[i]}{k} }\rceil

其中 \lceil{x}\rceil 表示对 x 向上取整。此时对于第 i 个水桶需要的「升级水桶」操作次数为 \max{0, m_i - \textit{bucket}[i]\。所以总的操作次数为

k + \sum_{j=0}^{n-1}{\max{0, m_j - \textit{bucket}[j]}

那么我们枚举「蓄水」操作次数的 k 即可。其中「蓄水」操作次数一定不会大于全部水缸的最大最低蓄水量。并且当 k 大于等于当前已经得到的最少操作总次数时，可以提前结束枚举。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        int n = bucket.size();
        int maxk = *max_element(vat.begin(), vat.end());
        if (maxk == 0) {
            return 0;
        }
        int res = INT_MAX;
        for (int k = 1; k <= maxk && k < res; ++k) {
            int t = 0;
            for (int i = 0; i < bucket.size(); ++i) {
                t += max(0, (vat[i] + k - 1) / k - bucket[i]);
            }
            res = min(res, t + k);
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        int n = bucket.length;
        int maxk = Arrays.stream(vat).max().getAsInt();
        if (maxk == 0) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int k = 1; k <= maxk && k < res; ++k) {
            int t = 0;
            for (int i = 0; i < bucket.length; ++i) {
                t += Math.max(0, (vat[i] + k - 1) / k - bucket[i]);
            }
            res = Math.min(res, t + k);
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int StoreWater(int[] bucket, int[] vat) {
        int n = bucket.Length;
        int maxk = vat.Max();
        if (maxk == 0) {
            return 0;
        }
        int res = int.MaxValue;
        for (int k = 1; k <= maxk && k < res; ++k) {
            int t = 0;
            for (int i = 0; i < bucket.Length; ++i) {
                t += Math.Max(0, (vat[i] + k - 1) / k - bucket[i]);
            }
            res = Math.Min(res, t + k);
        }
        return res;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def storeWater(self, bucket: List[int], vat: List[int]) -> int:
        n = len(bucket)
        maxk = max(vat)
        if maxk == 0:
            return 0
        res = float('inf')
        for k in range(1, maxk + 1):
            t = 0
            for i in range(n):
                t += max(0, (vat[i] + k - 1) // k - bucket[i])
            res = min(res, t + k)
        return res
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func storeWater(bucket []int, vat []int) int {
    n := len(bucket)
    maxk := 0
    for _, v := range vat {
        if v > maxk {
            maxk = v
        }
    }
    if maxk == 0 {
        return 0
    }
    res := math.MaxInt32
    for k := 1; k <= maxk && k < res; k++ {
        t := 0
        for i := 0; i < n; i++ {
            t += max(0, (vat[i] + k - 1) / k - bucket[i])
        }
        res = min(res, t+k)
    }
    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static int max(int a, int b) {
    return a > b ? a : b;
}

static int min(int a, int b) {
    return a < b ? a : b;
}

int storeWater(int* bucket, int bucketSize, int* vat, int vatSize) {
    int maxk = 0;
    for (int i = 0; i < vatSize; i++) {
        maxk = max(maxk, vat[i]);
    }
    if (maxk == 0) {
        return 0;
    }
    int res = INT_MAX;
    for (int k = 1; k <= maxk && k < res; ++k) {
        int t = 0;
        for (int i = 0; i < bucketSize; ++i) {
            t += max(0, (vat[i] + k - 1) / k - bucket[i]);
        }
        res = min(res, t + k);
    }
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var storeWater = function(bucket, vat) {
    const maxk = _.max(vat);
    if (maxk === 0) {
        return 0;
    }
    let res = Number.MAX_VALUE;
    for (let k = 1; k <= maxk && k < res; ++k) {
        let t = 0;
        for (let i = 0; i < bucket.length; ++i) {
            t += Math.max(0, Math.floor((vat[i] + k - 1) / k - bucket[i]));
        }
        res = Math.min(res, t + k);
    }
    return res;
};

复杂度分析

  • 时间复杂度：O(n \times C)，其中 n 为数组 bucket 的长度，C 为数组 vat 的范围。
  • 空间复杂度：O(1)，仅使用常量空间。

方法二：贪心 + 优先队列

思路与算法

因为「升级水桶」操作都在「蓄水」操作之前，所以若现在在「蓄水」操作前第 i 个水桶的容量为 bucket}’[i]，0 \le i < n，则需要「蓄水」的操作至少为

\max{\lceil{\textit{vat}[i]}{\textit{bucket}’[i]} }\rceil\

即此时总的操作次数为

\sum_{j = 0}^{n - 1}{(\textit{bucket}’[i] - \textit{bucket}[i])} + \max{\lceil{\textit{vat}[i]}{\textit{bucket}’[i]} }\rceil\

因为需要「蓄水」的操作次数只与 n 个水缸中需要「蓄水」操作的最大值决定。所以若此时我们想减少总的操作次数，我们只能尝试选择需要进行最多次「蓄水」操作的水缸，在进行「蓄水」前对其配备的水桶进行「升级水桶」操作，使得其需要的「蓄水」操作至少减少 1。

我们可以用「最大堆」（「优先队列」）来实现以上操作。我们以二元组 (\textit{cnt}_i, \textit{i}) 来表示第 i 个水缸需要的「蓄水」操作 cnt}_i 次。从初始时将每一个水缸对应的二元组加入「最大堆」，其中需要注意某若一个水缸需要的蓄水要求为 0 时可以直接忽略该水缸，和若某一个水缸配备的水桶初始容量为 0 时且水缸的蓄水要求大于 0 时，为了避免无法达到蓄水要求，此时需要进行一次「升级水桶」操作。然后我们每次尝试进行减小总的操作次数——从「最大堆」中取出需要「蓄水」操作最多的水桶，并进行「升级水桶」操作使得其需要的「蓄水」操作至少减少 1，然后再次放入「最大堆」中，并更新当前需要的总的操作次数最小值，直到当「升级水桶」的操作次数已经不能再减少总的操作次数为止：

  • 「升级水桶」的次数已经大于等于当前已得的总操作次数最小值；
  • 此时需要的「蓄水」操作等于 1。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int storeWater(vector<int>& bucket, vector<int>& vat) {
        int n = bucket.size();
        priority_queue<pair<int, int>> q;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (bucket[i] == 0 && vat[i]) {
                ++cnt;
                ++bucket[i];
            }
            if (vat[i] > 0) {
                q.emplace((vat[i] + bucket[i] - 1) / bucket[i], i);
            }
        }
        if (q.empty()) {
            return 0;
        }
        int res = INT_MAX;
        while (cnt < res) {
            auto [v, i] = q.top();
            res = min(res, cnt + v);
            if (v == 1) {
                break;
            }
            q.pop();
            int t = (vat[i] + v - 2) / (v - 1);
            cnt += t - bucket[i];
            bucket[i] = t;
            q.emplace((vat[i] + bucket[i] - 1) / bucket[i], i);
        }
        return res;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int storeWater(int[] bucket, int[] vat) {
        int n = bucket.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]);
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (bucket[i] == 0 && vat[i] != 0) {
                ++cnt;
                ++bucket[i];
            }
            if (vat[i] > 0) {
                pq.offer(new int[]{(vat[i] + bucket[i] - 1) / bucket[i], i});
            }
        }
        if (pq.isEmpty()) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        while (cnt < res) {
            int[] arr = pq.poll();
            int v = arr[0], i = arr[1];
            res = Math.min(res, cnt + v);
            if (v == 1) {
                break;
            }
            int t = (vat[i] + v - 2) / (v - 1);
            cnt += t - bucket[i];
            bucket[i] = t;
            pq.offer(new int[]{(vat[i] + bucket[i] - 1) / bucket[i], i});
        }
        return res;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int StoreWater(int[] bucket, int[] vat) {
        int n = bucket.Length;
        PriorityQueue<Tuple<int, int>, int> pq = new PriorityQueue<Tuple<int, int>, int>();
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (bucket[i] == 0 && vat[i] != 0) {
                ++cnt;
                ++bucket[i];
            }
            if (vat[i] > 0) {
                pq.Enqueue(new Tuple<int, int>((vat[i] + bucket[i] - 1) / bucket[i], i), -(vat[i] + bucket[i] - 1) / bucket[i]);
            }
        }
        if (pq.Count == 0) {
            return 0;
        }
        int res = int.MaxValue;
        while (cnt < res) {
            Tuple<int, int> tuple = pq.Dequeue();
            int v = tuple.Item1, i = tuple.Item2;
            res = Math.Min(res, cnt + v);
            if (v == 1) {
                break;
            }
            int t = (vat[i] + v - 2) / (v - 1);
            cnt += t - bucket[i];
            bucket[i] = t;
            pq.Enqueue(new Tuple<int, int>((vat[i] + bucket[i] - 1) / bucket[i], i), -(vat[i] + bucket[i] - 1) / bucket[i]);
        }
        return res;
    }
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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, [-((vat[i] + bucket[i] - 1) // 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, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])
        return res
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
func storeWater(bucket []int, vat []int) int {
    n := len(bucket)
    pq := make(priorityQueue, 0)
    cnt := 0
    for i := 0; i < n; i++ {
        if bucket[i] == 0 && vat[i] > 0 {
            cnt++
            bucket[i]++
        }
        if vat[i] > 0 {
            heap.Push(&pq, &item{priority: -(vat[i] + bucket[i] - 1) / bucket[i], index: i})
        }
    }
    if pq.Len() == 0 {
        return 0
    }
    res := math.MaxInt32
    for cnt < res {
        it := heap.Pop(&pq).(*item)
        v, i := -it.priority, it.index
        res = min(res, cnt+v)
        if v == 1 {
            break
        }
        t := (vat[i] + v - 2) / (v - 1)
        cnt += t - bucket[i]
        bucket[i] = t
        heap.Push(&pq, &item{priority: -(vat[i] + bucket[i] - 1) / bucket[i], index: i})
    }
    return res
}

type item struct {
    priority int
    index    int
}

type priorityQueue []*item

func (pq priorityQueue) Len() int {
    return len(pq)
}

func (pq priorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq priorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *priorityQueue) Push(x interface{}) {
    item := x.(*item)
    *pq = append(*pq, item)
}

func (pq *priorityQueue) Pop() interface{} {
    n := len(*pq)
    item := (*pq)[n-1]
    *pq = (*pq)[:n-1]
    return item
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
var storeWater = function(bucket, vat) {
    const n = bucket.length;
    const pq = new MaxHeap((a, b) => a[0] > b[0]);
    let cnt = 0;
    for (let i = 0; i < n; ++i) {
        if (bucket[i] === 0 && vat[i] !== 0) {
            ++cnt;
            ++bucket[i];
        }
        if (vat[i] > 0) {
            pq.add([Math.floor((vat[i] + bucket[i] - 1) / bucket[i]), i]);
        }
    }
    if (pq.size <= 0) {
        return 0;
    }
    let res = Number.MAX_VALUE;
    while (cnt < res) {
        const arr = pq.poll();
        const v = arr[0], i = arr[1];
        res = Math.min(res, cnt + v);
        if (v === 1) {
            break;
        }
        const t = Math.floor((vat[i] + v - 2) / (v - 1));
        cnt += t - bucket[i];
        bucket[i] = t;
        pq.add([Math.floor((vat[i] + bucket[i] - 1) / bucket[i]), i]);
    }
    return res;
};

class MaxHeap {
  constructor(compareFunc = (a, b) => a > b) {
    this.compare = compareFunc;
    this.heap = [];
  }

  get size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0];
  }

  add(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  poll() {
    if (this.size === 0) {
      return null;
    }
    if (this.size === 1) {
      return this.heap.pop();
    }
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return max;
  }

  heapifyUp() {
    let currentIndex = this.size - 1;
    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      if (this.compare(this.heap[currentIndex], this.heap[parentIndex])) {
        [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]];
        currentIndex = parentIndex;
      } else {
        break;
      }
    }
  }

  heapifyDown() {
    let currentIndex = 0;
    while (currentIndex < this.size) {
      let largestIndex = currentIndex;
      const leftChildIndex = 2 * currentIndex + 1;
      const rightChildIndex = 2 * currentIndex + 2;
      if (leftChildIndex < this.size && this.compare(this.heap[leftChildIndex], this.heap[largestIndex])) {
        largestIndex = leftChildIndex;
      }
      if (rightChildIndex < this.size && this.compare(this.heap[rightChildIndex], this.heap[largestIndex])) {
        largestIndex = rightChildIndex;
      }
      if (largestIndex !== currentIndex) {
        [this.heap[currentIndex], this.heap[largestIndex]] = [this.heap[largestIndex], this.heap[currentIndex]];
        currentIndex = largestIndex;
      } else {
        break;
      }
    }
  }
}

复杂度分析

  • 时间复杂度：O(n \times \log n + n \times \log{n} \times \sqrt{C})，其中 n 为数组 bucket 的长度，C 为数组 vat 的范围。「最大堆」中的一次存取操作的时间操作为 O(\log n)，初始化「最大堆」的时间复杂度为 O(n \times \log n)。在每一个水桶的「蓄水」次数收敛到 1 的复杂度渐进为 O(\sqrt{C})。
  • 空间复杂度：O(n)，其中 n 为数组 bucket 的长度，主要为「最大堆」的空间开销。
 Comments
On this page
LCP 33-蓄水