给植物浇水

记牢这套口诀:够浇就前进 1 步、余量减需求;不够就回河一趟加 2 乘 i 加 1 步、余量重置成 capacity 减需求。下面每一帧都在套它。

先认识花园。舞台这一排就是 7 株植物,从左到右下标 0 到 6,格子里的数字是它各自的需水量,比如植物 0 要 2 单位、植物 2 要 5 单位。它们站的位置正好等于下标,植物 3 就在 x = 3。水罐容量是 6,画面左边看不见的 x = -1 处有条河,专门用来灌满水罐。

出发。人现在在 x = -1 的河边,把水罐灌满,water = 6,已走步数 ans = 0。紫色指针指向植物 0,就是我们第一个要去浇的目标。注意从河边走到植物 0 本身也要花 1 步,这一步等下浇的时候一起算。

轮到植物 0,它需要 2 单位水。关键动作:拿水罐当前余量 6 和它的需水 2 比一比。余量 6 大于等于 2,够浇,不用回河。

够浇,直接动手。从上一株的位置往前走 1 步踏到植物 0,把它浇了,水罐余量从 6 减去 2 剩 4。步数只加这 1 步,ans 变成 1。植物 0 变绿,表示浇好了。

轮到植物 1,它需要 4 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 4 和它的需水 4 比一比。余量 4 大于等于 4,够浇,不用回河。

够浇,直接动手。从上一株的位置往前走 1 步踏到植物 1,把它浇了,水罐余量从 4 减去 4 剩 0。步数只加这 1 步,ans 变成 2。植物 1 变绿,表示浇好了。

轮到植物 2,它需要 5 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 0 和它的需水 5 比一比。余量 0 比 5 还小,不够完全浇灌,这一趟得先回河边。

水不够,先回河边。此刻人站在植物 1 那里,也就是 x = 1,一路后退到 x = -1 的河边,要走 2 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 2 步,ans 暂时是 4。植物 2 标红,提醒它就是那株让我们折返的。

灌满后再从河边走回来。从 x = -1 走到植物 2 要走 3 步,踏上去把它浇了。这一整趟折返合计 2 加 3 等于 5 步,正好是 2 乘 2 加 1。ans 一下子跳到 7,水罐余量变成 6 减 5 等于 1。植物 2 浇好变绿。

轮到植物 3,它需要 1 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 1 和它的需水 1 比一比。余量 1 大于等于 1,够浇,不用回河。

够浇,直接动手。从上一株的位置往前走 1 步踏到植物 3,把它浇了,水罐余量从 1 减去 1 剩 0。步数只加这 1 步,ans 变成 8。植物 3 变绿,表示浇好了。

轮到植物 4,它需要 2 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 0 和它的需水 2 比一比。余量 0 比 2 还小,不够完全浇灌,这一趟得先回河边。

水不够,先回河边。此刻人站在植物 3 那里,也就是 x = 3,一路后退到 x = -1 的河边,要走 4 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 4 步,ans 暂时是 12。植物 4 标红,提醒它就是那株让我们折返的。

灌满后再从河边走回来。从 x = -1 走到植物 4 要走 5 步,踏上去把它浇了。这一整趟折返合计 4 加 5 等于 9 步,正好是 2 乘 4 加 1。ans 一下子跳到 17,水罐余量变成 6 减 2 等于 4。植物 4 浇好变绿。

轮到植物 5,它需要 5 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 4 和它的需水 5 比一比。余量 4 比 5 还小,不够完全浇灌,这一趟得先回河边。

水不够,先回河边。此刻人站在植物 4 那里,也就是 x = 4,一路后退到 x = -1 的河边,要走 5 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 5 步,ans 暂时是 22。植物 5 标红,提醒它就是那株让我们折返的。

灌满后再从河边走回来。从 x = -1 走到植物 5 要走 6 步,踏上去把它浇了。这一整趟折返合计 5 加 6 等于 11 步,正好是 2 乘 5 加 1。ans 一下子跳到 28,水罐余量变成 6 减 5 等于 1。植物 5 浇好变绿。

轮到植物 6,它需要 4 单位水。左边蓝色的是已经浇好的植物。关键动作:拿水罐当前余量 1 和它的需水 4 比一比。余量 1 比 4 还小,不够完全浇灌,这一趟得先回河边。

水不够,先回河边。此刻人站在植物 5 那里,也就是 x = 5,一路后退到 x = -1 的河边,要走 6 步。到了河边把水罐重新灌满,water 回到 6。步数先记上这后退的 6 步,ans 暂时是 34。植物 6 标红,提醒它就是那株让我们折返的。

灌满后再从河边走回来。从 x = -1 走到植物 6 要走 7 步,踏上去把它浇了。这一整趟折返合计 6 加 7 等于 13 步,正好是 2 乘 6 加 1。ans 一下子跳到 41,水罐余量变成 6 减 4 等于 2。植物 6 浇好变绿。

七株植物全部浇完。回看一路:植物 0、1、3 是余量够、直接前进 1 步浇的;植物 2、4、5、6 都是余量不够、回河折返浇的,越往右回一趟越贵,因为后退和前进的距离都变长了。把每一步累加起来,总共走了 41 步,这就是答案。

边界想清:单株正好够是 1 步、每次余量不足就回河一趟、极端情况除第一株外几乎每株都回河。

面试重点:顺序固定所以一遍模拟、回河一趟是 2 乘 i 加 1 步、步数是 n 平方量级 int 够用。