分糖果 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 所示:

说明：

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

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

remaining=C−∑i=0i=pirm{remaining}= C - sum_{i=0}^{i=p}iremaining=C−i=0∑i=p​i

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

remaining=C−p(p+1)2rm{remaining} = C - frac{p(p+1)}{2}remaining=C−2p(p+1)​

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

0≤C−p(p+1)2<p+10 leq C - frac{p(p+1)}{2} < p+10≤C−2p(p+1)​<p+1

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

C−p(p+1)2≥0C - frac{p(p+1)}{2} geq 0C−2p(p+1)​≥0

C−p(p+1)2<p+1C - frac{p(p+1)}{2} < p+1C−2p(p+1)​<p+1

进而简化成：

p2+p−2C≤0p^2 + p - 2C leq 0p2+p−2C≤0

p2+3p+2−2C>0p^2 + 3p + 2 - 2C > 0p2+3p+2−2C>0

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

x1,2=−b±b2−4ac2ax_{1,2} = frac{-b pm sqrt{b^2-4ac}}{2a}x1,2​=2a−b±b2−4ac​​

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

p≤2C+14−12p leq sqrt{2C+frac{1}{4}} - frac{1}{2}p≤2C+41​​−21​

p>2C+14−32p > sqrt{2C+frac{1}{4}} - frac{3}{2}p>2C+41​​−23​

合并两个式子得：

2C+14−12<p≤2C+14−32 sqrt{2C+frac{1}{4}} - frac{1}{2} < p leq sqrt{2C+frac{1}{4}} - frac{3}{2}2C+41​​−21​<p≤2C+41​​−23​

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

p=floor(2C+14−12)p = rm{floor}(sqrt{2C+frac{1}{4}}-frac{1}{2})p=floor(2C+41​​−21​)

其中 $\mathrm{f}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{r}()$ 表示向下取整。

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

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

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

d[i]=i+(i+N)+(i+2N)+...+(i+(rows−1)N)=i×rows+Nrows(rows−1)2 begin{aligned} d[i] &= i + (i + N) + (i + 2N) + ... + (i + rm(rows -1)N) \ &= i times rm{rows} + Nfrac{rows(rows-1)}{2} end{aligned} d[i]​=i+(i+N)+(i+2N)+...+(i+(rows−1)N)=i×rows+N2rows(rows−1)​​

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

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

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

$$d[i]+=i+N\ast \mathrm{r}\mathrm{o}\mathrm{w}\mathrm{s}$$

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

$$d[\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{s}+1]+=\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}$$

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

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

p=floor(2C+14−12)p = rm{floor}(sqrt{2C+frac{1}{4}}-frac{1}{2})p=floor(2C+41​​−21​)

remaining=C−p(p+1)2rm{remaining} = C - frac{p(p+1)}{2}remaining=C−2p(p+1)​

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

d[i]=i×rows+Nrows(rows−1)2d[i] = i times rm{rows} + N frac{{rows(rows-1)}}{2}d[i]=i×rows+N2rows(rows−1)​

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

$$d[i]+=i+N\times \mathrm{r}\mathrm{o}\mathrm{w}\mathrm{s}$$

• 剩余的糖果则分给最后一人，即是第 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》问题的主要内容。