漫画：有趣的 “切蛋糕“ 问题

—————  第二天  —————

举个例子：

我们有5块蛋糕，

蛋糕的大小分别是  5 ， 17，25 ， 3 ， 15

我们有7位顾客，

他们的饭量分别是  2，5，7，9，12，14，20

（每个蛋糕大小和顾客食量都是小于1000的整数，蛋糕和顾客的数量不超过1000）

在分发蛋糕时，

有一个特殊的规则： 蛋糕可分不可合 。

什么意思呢？

一块较大的蛋糕，

可以切分成多个小块，

用来满足多个胃口较小的顾客：

但是，若干块较小的蛋糕， 不允许 合并成一块大蛋糕，

用来满足一个胃口较大的顾客：

最后的问题是： 给定蛋糕大小的集合cakes，

给定顾客饭量的集合mouths，

如何计算出这些蛋糕可以满足的最大顾客数量？

比如：输入cakes集合 {2，9}；

输入mouths集合 {5，4， 2，8}

正确返回：3

小灰的思路：

为了让更多的顾客吃饱，

肯定要优先满足食量小的顾客，

所以小灰决定使用 贪心算法 。

首先，把蛋糕和顾客从小到大进行排序：

按照上面的例子，排序结果如下：

接下来，让每一个蛋糕和顾客按照从左到右的顺序匹配。

如果蛋糕大于顾客饭量，则切分蛋糕；

如果蛋糕小于顾客饭量，则丢弃该蛋糕。

第1块蛋糕大小是3，第1个顾客饭量是2，

于是把蛋糕切分成2+1，满足顾客。

剩下的1大小蛋糕无法满足下一位顾客，丢弃掉。

第2块蛋糕大小是5，第2个顾客饭量是5，刚好满足顾客。

第3块蛋糕大小是15，第3个顾客饭量是7，

于是把蛋糕切分成7+8，满足顾客。

剩下的8大小蛋糕无法满足下一位顾客，丢弃掉。

第4块蛋糕大小是17，第4个顾客饭量是9，

于是把蛋糕切分成9+8，满足顾客。

剩下的8大小蛋糕无法满足下一位顾客，丢弃掉。

第5块蛋糕大小是25，第5个顾客饭量是12，

于是把蛋糕切分成12+13，满足顾客。

剩下的13大小蛋糕无法满足下一位顾客，丢弃掉。

这样一来，所有蛋糕都用完了，

由贪心算法得出结论，

最大能满足的顾客数量是5。

例子当中，

3的蛋糕满足2的顾客，

5的蛋糕满足5的顾客，

15的蛋糕满足12的顾客，

17的蛋糕满足7和9的顾客，

25的蛋糕满足14的顾客。

显然，面试官随意给出的吃法，满足了6个顾客。

————————————

这句话听起来有点绕，什么意思呢？

我们可以看看下面这张图：

其实道理很简单，

由于顾客的饭量是从小到大 排序 的，

优先满足饭量小的顾客，

才能尽量满足更多的人。

因此，在记录顾客饭量的数组中，

必定存在一段从最左侧开始的连续元素，

符合当前蛋糕所能满足的最多顾客组合。

这样一来，

我们的题目就从 寻找最大满足顾客数量 ，

转化成了 寻找顾客饭量有序数组中的最大满足临界点：

让我们先来回顾一下二分查找的思路：

1.选择中间元素，下标mid = （0 + 6）/2 = 3 ，因此中间元素是9：

2.判断9>5，选择元素9左侧部分的中间元素，

下标mid = （0+2）/2 = 1，因此中间元素是5：

3.判断5=5，查找结束。

但是，切蛋糕的问题比普通的二分查找要复杂得多，

因为我们要寻找的顾客饭量数组临界元素，

并不是简单地判断元素是否相等，

而是要验证给定的蛋糕能否满足临界元素之前的所有顾客。

如何来实现呢？

我们仍旧使用刚才的例子，演示一下详细过程：

第一步，寻找顾客数组的中间元素。

在这里，中间元素是9：

第二步，验证饭量从2到9的顾客能否满足。

子步骤1，遍历蛋糕数组，

寻找大于9的蛋糕，最终寻找到元素15。

子步骤2，饭量9的顾客吃掉15的蛋糕，还剩6大小。

子步骤3，重新遍历蛋糕数组，

寻找大于7的蛋糕，最终寻找到元素17。

子步骤4，饭量7的顾客吃掉17的蛋糕，还剩10大小。

子步骤5，重新遍历蛋糕数组，

寻找大于5的蛋糕，最终寻找到元素5。

子步骤6，饭量5的顾客吃掉5的蛋糕，还剩0大小。

子步骤7，重新遍历蛋糕数组，

寻找大于2的蛋糕，最终寻找到元素3。

子步骤8，饭量2的顾客吃掉3的蛋糕，还剩1大小。

到此为止，从2到9的所有顾客都被满足了，验证成功。

接下来，我们需要引入更多顾客，

从而试探出蛋糕满足的顾客上限。

第三步，重新寻找顾客数组的中间元素。

由于第二步验证成功，

所以我们要在元素9右侧的区域，

重新寻找中间元素。

显然，这个中间元素是14：

第四步，验证饭量从2到14的顾客能否满足。

这一步和第二步的思路是相同的，这里就不详细阐述了。

最终的验证结果是，从2到14的顾客能够满足。

接下来，我们还要引入更多顾客，

试探出蛋糕满足的顾客上限。

第五步，重新寻找顾客数组的中间元素。

由于第四步验证成功，

所以我们要在元素14右侧的区域，重新寻找中间元素。

显然，这个中间元素也就是唯一的元素20：

第六步，验证饭量从2到20的顾客能否满足。

这一步和第二步、第四步的思路是相同的，

这里就不详细阐述了。

最终的验证结果是，

从2到20的顾客 不能够 满足。

经过以上步骤，我们找到了最大满足顾客的临界点14，

从2到14共有6个顾客，

所以 给定蛋糕最大能满足的顾客数量是6 。

这段代码比较复杂，

需要说明几点：

1.主流程方法 findMaxFe ed ，执行各种初始化，控制二分查找流程。

2.方法 canFeed， 用于检验某一位置之前的顾客是否能被给定蛋糕满足。

3.数组 leftCakes ，用于临时存储剩余的蛋糕大小，每次重新设置中间下标时，这个数组需要被重置。

告诉大家一个好消息，

小灰的《漫画算法》全面上架啦，

在短短的两周里，

本书一度霸占着各大畅销榜榜首！

扫码查看详情

小灰把两年多以来积累的漫画作品进行了筛选和优化，

并加上了一些更为基础和系统的入门章节，

最终完成了本书的六大篇章：

本书是全彩印制，书中的每一章、每一节、每一句话、每一幅图、每一行代码，都经过了小灰和编辑们的精心打磨，力求用最为直白的方式把知识讲明白、讲透彻。

早期的漫画中存在一些叙述错误和表达不清晰的地方，小灰在本书中做了修正和补充；同时书中增加了许多全新的篇章，使得本书的内容更加系统和全面。

对于渴望学习算法的小伙伴，无论你是正在学习计算机专业的学生，还是已经进入职场的新人，亦或是拥有多年工作经验却不擅长算法的老手，这本《漫画算法》都能帮助你告别对算法的恐惧，认识算法、掌握算法。

扫码购买

新品8折优惠中