沉迷算法，无法自拔。

分蛋糕问题

给定蛋糕大小的集合

如上图所示：

第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，第4个顾客饭量是12，于是把蛋糕切分成12+13，满足顾客。剩下的13大小蛋糕无法满足下一位顾客，丢弃掉。 

这样一来，所有蛋糕都用完了，由贪心算法得出结论，最大能满足的顾客数量是5。  

但是！再此例子中，换一种分法如下图：

3的蛋糕满足2的顾客， 5的蛋糕满足5的顾客， 15的蛋糕满足12的顾客， 17的蛋糕满足7和9的顾客， 25的蛋糕满足14的顾客。 显然，此种吃法，满足了6个顾客。

如此看来，此种分蛋糕的方式是错误的。究其原因是因为没有抓住题目的关键点：当顾客从小到大排序之后，无论蛋糕大小如何，最多能满足的顾客组合中，一定有一个组合是连续的。

其实道理很简单，由于顾客的饭量是从小到大排序的，优先满足饭量小的顾客，才能尽量满足更多的人。 

 因此，在记录顾客饭量的数组中，必定存在一段从最左侧开始的连续元素，符合当前蛋糕所能满足的最多顾客组合。 

 这样一来，我们的题目就从寻找最大满足顾客数量，转化成了寻找顾客饭量有序数组中的最大满足临界点。

而找到数组中的​一个临界点，我们可以采用二分法查找

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

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

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

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

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

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

思路明确后，代码就呼之欲出了:

/**
 * 分蛋糕问题
 */
//剩余蛋糕数量
private static int[] leftCakes;
//蛋糕总量（不是数量，而是大小之和）
private static int totalCake = 0;
//浪费蛋糕量
private static int lostCake = 0;

/**
 * 子方法：检验顾客能否满足
 */
private static boolean canFeed(int[] mouths, int monthIndex, int sum) {
    if (monthIndex <= 0) {
        //递归边界
        return true;
    }
    //如果 蛋糕总量-浪费蛋糕量 小于当前的需求量，直接返回false，即无法满足
    if (totalCake - lostCake < sum) {
        return false;
    }
    //从小到大遍历蛋糕
    for (int i = 0; i < leftCakes.length; ++i) {
        if (leftCakes[i] >= mouths[monthIndex]) {
            //找到并吃掉匹配的蛋糕
            leftCakes[i] -= mouths[monthIndex];
            //剩余蛋糕小于最小的需求，变为浪费蛋糕
            if (leftCakes[i] < mouths[1]) {
                lostCake += leftCakes[i];
            }
            //继续递归，试图满足mid下标之前的需求
            if (canFeed(mouths, monthIndex - 1, sum)) {
                return true;
            }
            //无法满足需求，蛋糕状态回滚
            if (leftCakes[i] < mouths[1]) {
                lostCake -= leftCakes[i];
            }
            leftCakes[i] += mouths[monthIndex];
        }
    }
    return false;
}

/**
 * 主流程方法
 *
 * @param cakes  蛋糕数组
 * @param mouths 顾客数组
 * @return 人数
 */
public int findMaxFeed(int[] cakes, int[] mouths) {
    //蛋糕升序排列，并把0下标空出
    int[] cakesTemp = Arrays.copyOf(cakes, cakes.length + 1);
    Arrays.sort(cakesTemp);
    for (int cake : cakesTemp) {
        totalCake += cake;
    }
    //顾客胃口升序排列，并把0下标空出
    int[] mouthsTemp = Arrays.copyOf(mouths, mouths.length + 1);
    Arrays.sort(mouthsTemp);
    leftCakes = new int[cakes.length + 1];
    //需求之和（下标0的元素是0个人的需求之和，下标1的元素是第1个人的需求之和，下标2的元素是第1,2个人的需求之和.....）
    int[] sum = new int[mouths.length + 1];
    for (int i = 1; i <= mouths.length; i++) {
        sum[i] = sum[i - 1] + mouthsTemp[i];
    }
    //left和right用于计算二分查找的“中点”
    int left = 1, right = mouths.length;
    //如果胃口总量大于蛋糕总量，right指针左移
    while (sum[right] > totalCake) {
        right--;
    }
    //中位指针，用于做二分查找
    int mid = ((left + right) >> 1);
    while (left <= right) {
        //重置剩余蛋糕数组
        leftCakes = Arrays.copyOf(cakesTemp, cakesTemp.length);
        //重置浪费蛋糕量
        lostCake = 0;
        //递归寻找满足需求的临界点
        if (canFeed(mouthsTemp, mid, sum[mid])) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        mid = ((left + right) >> 1);
    }
    //最终找到的是刚好满足的临界点
    return mid;
}

代码说明：

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

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

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

4.方法canFeed，可以采用更优质的算法解决。