喂食仓鼠的最小食物桶数

记牢这套口诀:见仓鼠先看右,右边空位就往右放让一桶喂两只;右边堵住再往左放;左右皆堵就无解。下面从最左边一格一格扫。

街道全貌 · 先数清楚有几只仓鼠：先把这条街看清楚。H 是仓鼠,点是空位。这条街上有四只仓鼠,分别蹲在下标 0、2、4、5 的位置。我们要在空位上放桶,把它们全喂到,而且桶要放得最少。

喂食规则 · 一个桶能照顾左右两只：把规则再捋一遍:一只仓鼠只要它紧挨着的左边一格,或者右边一格有桶,就算喂到了。反过来看,一个桶其实能同时照顾它左右两边的仓鼠,这正是我们能少放桶的地方。

指针 i 从下标 0 出发：用一个指针 i 从最左边开始,从左往右扫。ans 记已经放了几个桶,现在是 0。指针先停在下标 0。

下标 0 是仓鼠 · 必须给它安排桶：指针停在下标 0,这里是个 H,有一只仓鼠。它必须被喂到,也就是左边或右边得挨着一个桶。按口诀,先看它右边能不能放。

下标 0 左边是墙 · 只能指望右边：顺带说一句,下标 0 的左边已经是街道尽头,越界了,根本没有空位可放。所以对这只仓鼠来说,右边是唯一的指望。正好也符合我们优先往右放的原则。

看右边 · 下标 1 是空位：看它右边,下标 1 是个点,是空位。太好了,能往右放。这里藏着贪心的小心思:右边的桶不光喂当前这只,还可能顺带喂到再往右的那只仓鼠,所以能往右就优先往右。

在下标 1 放桶 · ans 加到 1：就在下标 1 放一个桶,涂成绿色。这样下标 0 的仓鼠右边挨着桶了,喂饱,标成蓝色。ans 加到 1。

一桶喂两只 · 桶 1 顺带喂到下标 2：关键一步来了。下标 1 的这个桶,右边正好是下标 2 的仓鼠,所以这一个桶把下标 0 和下标 2 两只仓鼠一起喂了。既然下标 2 已经安顿好,指针就多跳一格,越过下标 1 和 2,直接蹦到下标 3,你看指针现在就停在下标 3 上,省得回头重复看。这就是优先往右放换来的好处。

回头确认 · 下标 2 的仓鼠已被桶 1 喂到：指针已经停在下标 3 了,这里只是回头看一眼下标 2 那只仓鼠,并不是把指针挪回去重新扫它。它的左边就是下标 1 的桶,规则说左邻有桶就算喂到,所以它是被顺带喂饱的,不用再单独为它花一个桶。你看,一个桶服务两只,桶数就这么省下来了。

下标 3 是空位 · 没有仓鼠,继续：指针落到下标 3,这里是个点,空位,没有仓鼠要照顾。空位本身不需要我们做任何决定,直接往右走。

下标 4 是仓鼠 · 又要安排桶：走到下标 4,又是一只仓鼠。老规矩,先看它右边能不能放桶。

看右边 · 下标 5 也是仓鼠,放不下：看右边,下标 5 偏偏也是一只仓鼠,不是空位,桶塞不进去。右边这条路堵住了,标成红色。别急,还有左边可以退一步。

退一步看左边 · 下标 3 是空位：右边堵住,回头看左边,下标 3 是个点,空位。那就往左放,先把下标 4 这只仓鼠喂上要紧。注意这是右边放不下时的退路,不是首选。

在下标 3 放桶 · ans 加到 2：在下标 3 放一个桶,涂绿。下标 4 的仓鼠左边挨着桶了,喂饱,标蓝。ans 加到 2。这次因为往左放,右边没有第二只能顺带喂,指针就正常往右走一格。

下标 5 是仓鼠 · 最后一只：指针来到下标 5,就是刚才右边那只仓鼠,它还没被喂。继续给它安排,还是先看右边。

看右边 · 下标 6 是空位：它右边是下标 6,一个点,空位。能往右放,那就往右放,依然是优先右边这条原则。

在下标 6 放桶 · ans 加到 3：在下标 6 放一个桶,涂绿。下标 5 的仓鼠右边挨着桶了,喂饱,标蓝。ans 加到 3。至此四只仓鼠全部有着落。

指针越过街尾 · 扫描结束：指针越过街道最右边,循环结束。回头看,下标 0、2、4、5 四只仓鼠全都标成了蓝色,一个不落全喂饱了。

一览 · 四只仓鼠全部喂饱：把全局再扫一眼,四只蓝色的仓鼠都被绿色的桶挨着照顾到了。绿色的桶一共三个,分别在下标 1、3、6。三个桶喂饱四只仓鼠,靠的就是让桶 1 一桶喂了两只。

回放 · 三个桶喂饱四只仓鼠,答案 3：回放整条思路。从左往右扫,遇到仓鼠优先往右放桶好让一桶喂两只,右边放不下才退而往左放,哪边都放不了就返回 -1。数一数绿色的桶,一共三个,这就是喂饱所有仓鼠的最少桶数,答案是 3。

边界想清:孤零一只 H 无解、单只两边空位一个够、被仓鼠夹住无解、隔太远各放各的。

面试重点:优先右放的贪心正确性、右放多跳一格、桶只能放空位这条约束是无解的根源。