LeetCode 分糖果 II

分糖果 II

题目来源：https://leetcode-cn.com/problems/distribute-candies-to-people

题目

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

示例 1：

输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：

输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。

提示：

1 <= candies <= 10^9
1 <= num_people <= 1000

解题思路

思路：等差数列求和

用数学 “等差数列求和” 的方法来解决这个问题。先来逐步推导公式。

由题意可知，除了最后一份糖果的数量是由剩余的糖果数量决定，其他已分配的糖果数量是从 1 开始构成的等差数列。

如下图例 1 所示:

图例 1

说明：

$p$ ：表示数列元素， $C$ ：表示糖果总数量

假设数列一共有 $p$ 个元素，剩余的糖果就是糖果数量 $C$ 与等差数列前 $p$ 项的差。

$\rm{remaining}= C - \sum_{i=0}^{i=p}i$

根据等差数列求和公式可得:

$\rm{remaining} = C - \cfrac{p(p+1)}{2}$

根据题意，剩余的糖果数量是大于等于0，小于下一份分配糖果的数量 $p+1$ ，所以

$0 \leq C - \cfrac{p(p+1)}{2} < p+1$

将上面的式子转化为下面两个不等式：

$C - \cfrac{p(p+1)}{2} \geq 0$

$C - \cfrac{p(p+1)}{2} < p+1$

进而简化成：

$p^2 + p - 2C \leq 0$

$p^2 + 3p + 2 - 2C > 0$

$p$ 代表的等差数列的元素，也是本题中分配的糖果数量，这个值必定是大于 0 的一个数值，根据求根公式：

$x_{1,2} = \cfrac{-b \pm \sqrt{b^2-4ac}}{2a}$

可以求得上面两个不等式的取值范围的分别为：

$p \leq \sqrt{2C+\frac{1}{4}} - \frac{1}{2}$

$p > \sqrt{2C+\frac{1}{4}} - \frac{3}{2}$

合并两个式子得：

$\sqrt{2C+\frac{1}{4}} - \frac{1}{2} < p \leq \sqrt{2C+\frac{1}{4}} - \frac{3}{2}$

这个区间只有一个整数，因此可得 $p$ :

$p = \rm{floor}(\sqrt{2C+\frac{1}{4}}-\frac{1}{2})$

其中 $\rm{floor()}$ 表示向下取整。

先看完整分配糖果的回合数：

根据上面的推导公式，可得 $p$ 也表示已经完整分配的份数。那么回合数则为：rows = p // N，N 这里表示人数。

那么在 rows 个完整的回合当中，第 i 个人获得糖果总数数量：

$\begin{aligned} d[i] &= i + (i + N) + (i + 2N) + ... + (i + \rm(rows -1)N) \\ &= i \times \rm{rows} + N\cfrac{rows(rows-1)}{2} \end{aligned}$

再看不完整分配糖果的回合：

因为糖果会有不够的时候，那么最后一个回合可能就不完整。可能其中有一部分人会收到完整的糖果分配数量。

那么，可以计算出，完整分配到糖果的人数为 cols = p % N。这里这些人都比其他人多一份完整的糖果数量。

$d[i] += i + N * \rm{rows}$

那么最后一位可得到分配糖果即是剩余的糖果。

$d[\rm{cols} + 1] += {remaining}$

根据上面的推导，可总结以下具体的思路：

先计算出完整礼物的份数，以及最后一份糖果的数量：

$p = \rm{floor}(\sqrt{2C+\frac{1}{4}}-\frac{1}{2})$

$\rm{remaining} = C - \frac{p(p+1)}{2}$

完整的回合数为：rows = p // N，在这些完整的回合数中，每人拥有的糖果数量为：

$d[i] = i \times \rm{rows} + N\cfrac{{rows(rows-1)}}{2}$

在不完整的回合当中，一部分人可再得一份完整的糖果数:

$d[i] += i + N \times \rm{rows}$

剩余的糖果则分给最后一人，即是第 p % N 个人后面的人。
返回分配糖果的数组 d。

代码实现

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        N = num_people
        C = candies

        # 完整分配的糖果份数
        p = int((2 * C + 0.25) ** 0.5 - 0.5)
        # 剩余的糖果数
        remaining = int(C - p * (p + 1) * 0.5)
        # 回合数，以及最后一个回合分配到完整糖果数的人数
        rows, cols = p // N, p % N

        # 构建分配糖果的数组
        d = [0] * N

        # 遍历，这里 i 是从 0 开始的
        # 根据上面的公式计算式，需注意这一点
        for i in range(N):
            # 获得完整糖果数回合，每个人的糖果数
            d[i] = (i + 1) * rows + N * int(rows * (rows - 1) * 0.5)
            # 最后一个回合，一部分获得完整糖果数，需要额外加上
            if i < cols:
                d[i] += i + 1 + N * rows
        # 最后分配的一个人，分到剩余的糖果
        d[cols] += remaining

        # 返回分配的糖果数组
        return d

实现结果

以上就是使用数学方法《等差数列求和》，解决《分糖果 II》问题的主要内容。

欢迎关注微信公众号《书所集录》