一、题目背景

有 n 个孩子和 m 个苹果，每个孩子至少分一个，且相邻两个孩子的苹果数差值不能超过 1，求在满足条件的前提下，小明（第 k 个孩子）最多可以分到多少苹果？

二、思路分析

相邻两个孩子的苹果数量不能大于一而且小明需要尽可能的多分，所以最后肯定是一个以小明为峰顶的一个“山峰”形状。

所以问题的关键就是我们假设小明分到了 x 个苹果，然后根据小明的位置分别计算出左右两边需要的苹果数量，并判断数量是否足够，如果足够的话就将加 x 加一然后继续判断，直到 m 个苹果不够分为止。

三、关键实现逻辑

关键在于苹果数量的计算，现在我们假设分给了小明 x 个苹果，然后小明的位置在 k，他左边有 k-1 个人，右边有 n-k 个人，现在以从左边开始举例子（应为右边的计算方式也是一样）。

这里要分两种情况讨论一下：

1、x - 1 >= k - 1

这种情况下我们可以简单的计算苹果的数量，就是一个等差数列，将首项加上未项乘以项数除以 2 即可得到结果。

2、x - 1 < k - 1

在这种情况下，其实是由一个从一开始的等差数列加上一段全一组成的，计算公式就是在等差数列和的基础上加上全一段的长度（k - 1 - (x - 1)）。

好了，现在来实现这个函数：

// 构造从 x 向外递减的数列（每人至少 1）
    private long countApple(int x, int len) {
        if (x >= len) {
            long first = x - len;
            long last = x - 1;
            return (first + last) * len / 2;
        } else {
            long full = (long)(x - 1 + 1) * (x - 1) / 2;
            long ones = len - (x - 1);
            return full + ones;
        }
    }

下面是实现代码：

class Solution {
    public int maxApples(int n, int m, int k) {
        int left = k - 1;
        int right = n - k;
        int ans = 1;
        // 注意这里x直接从2开始
        for (int x = 2; x <= m; x++) {
            long total = getApple(x, left, right);
            if (total <= m) {
                ans++;
            } else {
                break;
            }
        }
        return ans;
    }

    public long getApple(int x, int left, int right) {
        return countApple(x, left) + countApple(x, right) + x;
    }

    public long countApple(int x, int len) {
        if(x >= len) {
            long first = x - len;
            long end = x - 1;
            // 满足要求就是等差数列求和
            return (first + end) * len / 2;
        } else {
            // 否则就是两部分相加
            long part1 = (long) (1 + x - 1) * (x - 1) / 2;
            long part2 = len - (x - 1);
            return part1 + part2;
        }
    }
}

可以发现，我们是从 x = 2 即两个苹果开始一个一个累加的，最终在（1， m）中找到满足要求的数，这显然是可以通过使用二分查找来优化的，下面给出完整的二分实现代码。

四、完整代码

class Solution {
    public int maxApples(int n, int m, int k) {
        int left = k - 1;
        int right = n - k;
        int ans = 1;
        // 使用二分优化
        int low = 1;
        int high = m;
        while (low <= high) {
            int mid = low + (right - low) / 2;
            long total = getApple(mid, left, right);
            if (total <= m) {
                // 满足条件将mid赋给ans同时将mid变大尝试更多的分法
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    public long getApple(int x, int left, int right) {
        return countApple(x, left) + countApple(x, right) + x;
    }

    public long countApple(int x, int len) {
        if(x >= len) {
            long first = x - len;
            long end = x - 1;
            // 满足要求就是等差数列求和
            return (first + end) * len / 2;
        } else {
            // 否则就是两部分相加
            long part1 = (long) (1 + x - 1) * (x - 1) / 2;
            long part2 = len - (x - 1);
            return part1 + part2;
        }
    }
}

五、心得体会

这道题是我在做一家公司的笔试题的时候出现的，当时没有想清楚怎么计算左右两边的苹果数量（还是太菜了），只是想到了最后的形状是一个“堆”，但是对于边界的情况没有想清楚，这片文章就算是一个总结吧，希望能够激励自己继续努力。