给植物浇水 图解题解

这道题到底在问什么

输入

plants=[2,2,3,3], capacity=5

输出

14

输入

plants=[7,7,7,7,7,7,7], capacity=8

输出

49

最优解：一步一步想明白

1. 3记牢这套口诀:够浇就前进 1 步、余量减需求;不够就回河一趟加 2 乘 i 加 1 步、余量重置成 capacity 减需求。下面每一帧都在套它。
2. 4先认识花园。舞台这一排就是 7 株植物,从左到右下标 0 到 6,格子里的数字是它各自的需水量,比如植物 0 要 2 单位、植物 2 要 5 单位。它们站的位置正好等于下标,植物 3 就在 x = 3。水罐容量是 6,画面左边看不见的 x = -1 处有条河,专门用来灌满水罐。
3. 5出发。人现在在 x = -1 的河边,把水罐灌满,water = 6,已走步数 ans = 0。紫色指针指向植物 0,就是我们第一个要去浇的目标。注意从河边走到植物 0 本身也要花 1 步,这一步等下浇的时候一起算。
4. 6轮到植物 0,它需要 2 单位水。关键动作:拿水罐当前余量 6 和它的需水 2 比一比。余量 6 大于等于 2,够浇,不用回河。
5. 7够浇,直接动手。从上一株的位置往前走 1 步踏到植物 0,把它浇了,水罐余量从 6 减去 2 剩 4。步数只加这 1 步,ans 变成 1。植物 0 变绿,表示浇好了。
6. 8轮到植物 1,它需要 4 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 4 和它的需水 4 比一比。余量 4 大于等于 4,够浇,不用回河。
7. 9够浇,直接动手。从上一株的位置往前走 1 步踏到植物 1,把它浇了,水罐余量从 4 减去 4 剩 0。步数只加这 1 步,ans 变成 2。植物 1 变绿,表示浇好了。
8. 10轮到植物 2,它需要 5 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 0 和它的需水 5 比一比。余量 0 比 5 还小,不够完全浇灌,这一趟得先回河边。
9. 11水不够,先回河边。此刻人站在植物 1 那里,也就是 x = 1,一路后退到 x = -1 的河边,要走 2 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 2 步,ans 暂时是 4。植物 2 标红,提醒它就是那株让我们折返的。
10. 12灌满后再从河边走回来。从 x = -1 走到植物 2 要走 3 步,踏上去把它浇了。这一整趟折返合计 2 加 3 等于 5 步,正好是 2 乘 2 加 1。ans 一下子跳到 7,水罐余量变成 6 减 5 等于 1。植物 2 浇好变绿。
11. 13轮到植物 3,它需要 1 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 1 和它的需水 1 比一比。余量 1 大于等于 1,够浇,不用回河。
12. 14够浇,直接动手。从上一株的位置往前走 1 步踏到植物 3,把它浇了,水罐余量从 1 减去 1 剩 0。步数只加这 1 步,ans 变成 8。植物 3 变绿,表示浇好了。
13. 15轮到植物 4,它需要 2 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 0 和它的需水 2 比一比。余量 0 比 2 还小,不够完全浇灌,这一趟得先回河边。
14. 16水不够,先回河边。此刻人站在植物 3 那里,也就是 x = 3,一路后退到 x = -1 的河边,要走 4 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 4 步,ans 暂时是 12。植物 4 标红,提醒它就是那株让我们折返的。
15. 17灌满后再从河边走回来。从 x = -1 走到植物 4 要走 5 步,踏上去把它浇了。这一整趟折返合计 4 加 5 等于 9 步,正好是 2 乘 4 加 1。ans 一下子跳到 17,水罐余量变成 6 减 2 等于 4。植物 4 浇好变绿。
16. 18轮到植物 5,它需要 5 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 4 和它的需水 5 比一比。余量 4 比 5 还小,不够完全浇灌,这一趟得先回河边。
17. 19水不够,先回河边。此刻人站在植物 4 那里,也就是 x = 4,一路后退到 x = -1 的河边,要走 5 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 5 步,ans 暂时是 22。植物 5 标红,提醒它就是那株让我们折返的。
18. 20灌满后再从河边走回来。从 x = -1 走到植物 5 要走 6 步,踏上去把它浇了。这一整趟折返合计 5 加 6 等于 11 步,正好是 2 乘 5 加 1。ans 一下子跳到 28,水罐余量变成 6 减 5 等于 1。植物 5 浇好变绿。
19. 21轮到植物 6,它需要 4 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 1 和它的需水 4 比一比。余量 1 比 4 还小,不够完全浇灌,这一趟得先回河边。
20. 22水不够,先回河边。此刻人站在植物 5 那里,也就是 x = 5,一路后退到 x = -1 的河边,要走 6 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 6 步,ans 暂时是 34。植物 6 标红,提醒它就是那株让我们折返的。
21. 23灌满后再从河边走回来。从 x = -1 走到植物 6 要走 7 步,踏上去把它浇了。这一整趟折返合计 6 加 7 等于 13 步,正好是 2 乘 6 加 1。ans 一下子跳到 41,水罐余量变成 6 减 4 等于 2。植物 6 浇好变绿。
22. 24七株植物全部浇完。回看一路:植物 0、1、3 是余量够、直接前进 1 步浇的;植物 2、4、5、6 都是余量不够、回河折返浇的,越往右回一趟越贵,因为后退和前进的距离都变长了。把每一步累加起来,总共走了 41 步,这就是答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        ans, water = 0, capacity
        for i, p in enumerate(plants):
            if water >= p:
                water -= p
                ans += 1
            else:
                water = capacity - p
                ans += i * 2 + 1
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int wateringPlants(vector<int>& plants, int capacity) {
        int ans = 0, water = capacity;
        for (int i = 0; i < plants.size(); ++i) {
            if (water >= plants[i]) {
                water -= plants[i];
                ans += 1;
            } else {
                water = capacity - plants[i];
                ans += i * 2 + 1;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int wateringPlants(int[] plants, int capacity) {
        int ans = 0, water = capacity;
        for (int i = 0; i < plants.length; ++i) {
            if (water >= plants[i]) {
                water -= plants[i];
                ans += 1;
            } else {
                water = capacity - plants[i];
                ans += i * 2 + 1;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问