題目連結:
題目意譯:
你想要用澆花器幫你的花園中的 n 株植物澆水。植物們排成一列並且從左至右編號為 0 到 n - 1,其中第 i 株植物位於 x = i。現有一條河位於 x = -1,你可以在那裡裝滿你的澆花器。
每株植物各自需要某特定量的水。而你將會按照以下方式來澆花:
從左至右依序為每株植物澆花。
當澆完目前這株植物後,如果你沒有足夠的水可以完整澆灌下一株植物,則回到河邊將澆花器重新裝滿。
你不得提早重新裝滿澆花器。
你現正位於那條河(即 x = -1)。在 x 軸上移動一單位需要一步。
(譯者注:一開始的澆花器是滿的(或者是全空的,然後依據規則在澆第 0 株植物前裝滿)。這點並沒有寫在原英文題目敘述中。而是只能從範例測資看出來)
給定一個索引值從 0 開始有著 n 個整數的整數陣列 plants,其中 plants[i] 為第 i 株植物需要的水量,以及給定一個整數 capacity 代表著澆花器的容量。回傳將所有植物澆完水所需之步數。
限制:
n == plants.length
1 ≦ n ≦ 1000
1 ≦ plants[i] ≦ 10 ^ 6
max(plants[i]) ≦ capacity ≦ 10 ^ 9
範例測資:
範例 1:
輸入: plants = [2,2,3,3], capacity = 5
輸出: 14
解釋: 開始於河邊並有著裝滿的澆花器:
- 走到植物 0(1 步)並澆花。澆花器剩 3 單位的水。
- 走到植物 1(1 步)並澆花。澆花器剩 1 單位的水。
- 由於無法完整澆灌植物 2,走回到河邊裝滿澆花器(2 步)。
- 走到植物 2(3 步)並澆花。澆花器剩 2 單位的水。
- 由於無法完整澆灌植物 3,走回到河邊裝滿澆花器(3 步)。
- 走到植物 3(4 步)並澆花。
需要步數 = 1 + 1 + 2 + 3 + 3 + 4 = 14。
範例 2:
輸入: plants = [1,1,1,4,2,3], capacity = 4
輸出: 30
解釋: 開始於河邊並有著裝滿的澆花器:
- 為植物 0 、 1 、 2 澆水(3 步)。回到河邊(3 步)。
- 為植物 3 澆水(4 步)。回到河邊(4 步)。
- 為植物 4 澆水(5 步)。回到河邊(5 步)。
- 為植物 5 澆水(6 步)。
需要步數 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30。
範例 3:
輸入: plants = [7,7,7,7,7,7,7], capacity = 8
輸出: 49
解釋: 你在為每株植物澆花前都必須重新裝滿澆花器。
需要步數 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49。
解題思維:
沒什麼特別的,就是單純地模擬即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。