1103-分糖果 II(Distribute Candies to People)

原文链接: https://leetcode-cn.com/problems/distribute-candies-to-people

英文原文

We distribute some number of candies, to a row of n = num_people people in the following way:

We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.

Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.

This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).

Return an array (of length num_people and sum candies) that represents the final distribution of candies.

Example 1:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

Example 2:

Input: candies = 10, num_people = 3
Output: [5,2,3]
Explanation: 
On the first turn, ans[0] += 1, and the array is [1,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0].
On the third turn, ans[2] += 3, and the array is [1,2,3].
On the fourth turn, ans[0] += 4, and the final array is [5,2,3].

Constraints:

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

中文题目

排排坐，分糖果。

我们买了一些糖果 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

通过代码

高赞题解

相信同学在看官方题解里面的数学方法里面时，会看到这样的式子：
$$\sqrt{2 C+\frac{1}{4}}-\frac{3}{2}<p \leq \sqrt{2 C+\frac{1}{4}}-\frac{1}{2}$$
或者是这个代码：

p = int((2 * candies + 0.25)**0.5 - 0.5)

“我擦，这是什么鬼？？？”
“咦！这玩意到底咋来的？”

我猜不少同学内心会这样想，我第一次看见数学解法的代码时也是一脸懵逼的。本帖会详细讲解我是怎么理解这个数学方法的，以及数学方法里面的每一步是怎么得到的，希望能帮助大家顺利理解。这里首先过一遍普通方法，这会帮大家加深对题目各个要素的记忆。

1. 普通方法

思想：对小朋友们进行遍历，每次都发小朋友们应得数量的糖，直到剩下的糖不足以分发应得数量，就直接给最后那位倒霉孩子

代码实现时，有一些细节技巧，大家可以仔细品一品

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        # 给小朋友们每人发个碗，用于装糖
        kids = [0] * num_people
        # 初始化第一轮
        i = 0

        # 只要糖还有，咱就继续发
        while candies > 0:
            # 这个i%num_people就很棒，随着i的增长，i对num_people进行取余数
            # 返回的数会一直是相应小朋友的正确下标
            # 用+=进行累加每一轮的新发的糖果
            # min的作用是，如果有一天糖不够了，就把那些最后剩余的糖给最后那个孩子
            kids[i % num_people] += min(i + 1, candies)
            
            # 手中糖的数量要记得减去每次发糖的数量
            candies -= i + 1
            # 这个小朋友发完了，下一位
            i += 1

        return kids

2. 数学方法

主要思想：给小朋友们发n次糖，每次发n个，假设最后的倒霉孩子拿不到完整的n+1个，而是c个，显然可以对前n项进行等差数列求和，然后根据c的限制条件构建不等式方程组，再进行求解即可得到结果p，意为我们可以完整无缺地发p次糖果，解出p可以发推出c，最后进行遍历，注意一下那个倒霉孩子即可。

注意，如果看不懂这个主要思想没关系，咱们来慢慢地捋一捋

首先我们手上有一把糖，眼前有一群嗷嗷待哺的小朋友等着你发糖。暂时先不考虑小朋友的数量，那么根据题意我们可以假设，如果每个小朋友都很幸运地能拿到完整的糖果，这就说明我们要发n次，每次发n个糖。

举个例子：我们手上有6个糖果，第1次发1个，第2次2个，第3次3个。这就很完美~

再看这个1,2,3,…,n的形式，可以联想到等差数列求和公式：
$$ 1 + 2 + 3 + … + n = \frac{n(n+1)}{2}$$
这个式子就能根据糖果的数量反推出n，即要发多少次糖。你可能会说，这是所有小朋友们都能拿到完整糖果的情况，没有考虑那个拿不到完整糖果的倒霉孩子。别急，咱们这里假设一个数值R作为最后那一份不完美糖果的数量。那么这个R存在如下性质：
$$ 0 \leq R < n + 1$$
这个式子就是说，最后这个倒霉孩子得到的糖果数量一定是大于等于0的，如果等于0，说明是完美无缺发给了所有小朋友。小于n+1是因为，如果R等于n+1的话，就使得完美的情况再次发生，即第n+1次发了n+1个糖。所以R必须是小于n+1的。

用C指代candies，所以我们手上总共的糖果数量可以写作：
$$ C = \frac{n(n+1)}{2} + R $$

这样，我们就可以对上面的不等式方程组进行推导：

$$
0 \leq C - \frac{n(n+1)}{2} <n+1
$$
写出这两个不等式方程组：
$$
\left{\begin{array}{l}
0 \leq C-\frac{n(n+1)}{2} \
C-\frac{n(n+1)}{2}<n+1
\end{array}\right.
$$
对两个不等式方程组进行简化，两边乘以-2，再移项，合并同类项
$$
\left{\begin{array}{l}
n^2 + n - 2C \leq 0 \
n^2 + 3n + 2 - 2C>0
\end{array}\right.
$$
到这里就很有意思了，相信大家都知道求根公式：
$$
x_{1,2}=\frac{-b \pm \sqrt{b^{2}-4 a c}}{2 a}
$$
我们知道n代表了发多少次糖，这必然是一个大于0的数，所以我们可以求出第一个方程组的根：
$$
n \leq \sqrt{2 C+\frac{1}{4}}-\frac{1}{2}
$$
同理，基于n必须为大于0的数，第二个不等式方程的根为：
$$
n > \sqrt{2 C+\frac{1}{4}}-\frac{3}{2}
$$
两个根进行合并之后就有：
$$
\sqrt{2 C+\frac{1}{4}}-\frac{3}{2}<n \leq \sqrt{2 C+\frac{1}{4}}-\frac{1}{2}
$$
因为C代表candies，是给定的数，所我们可以把$\sqrt{2 C+\frac{1}{4}}$看做一个常数$Constant$

可以清晰地看到n的取值范围变成了：
$$
Constant - 1.5<n \leq Constant-0.5
$$
这个范围的大小就是$Constant-0.5 - (Constant - 1.5) = 1$

这就说明区间内只有一个整数，这个整数就是我们最终完美无缺分发糖果的次数，用p进行指代。这时p就等于区间的上界向下取整，一是因为上界是小于等于符号，二是因为向下取整不会出界，所以有：
$$
p = (Constant - 0.5), 向下取整
$$
即
$$
p=\text { floor }\left(\sqrt{2 C+\frac{1}{4}}-\frac{1}{2}\right)
$$

这里的floor()函数表示向下取整的意思，python里面可以用int()表示，如int(1.8)就等于1

那么用python写出这个代码的话就是：

p = int((2 * candies + 0.25)**0.5 - 0.5)

“卧槽！这不就是之前那个代码么！”
各位亲，惊不惊喜意不意外！

到这里，大家就可以去喝一杯卡布奇诺了，因为后面的过程就变得简单了起来~
一杯卡布奇诺送给大家~

咖啡 ♂ 时间

喝完咖啡，我们再来看。显然，除了那个倒霉孩子以外，我们一共会进行p次完美地发糖果

对于剩余糖果数量R，根据式子$C=\frac{n(n+1)}{2}+R$，把求得的p代入n中即可，代码就是：

R = int(candies - (p + 1) * p * 0.5)

到这里，我们可以假设小朋友有n个人，这就说明我们就要发p//n轮，用rows指代。细心的你可能会考虑到p<n时的情况，是不是需要对rows加个1呢?

我想说，别急，这里咱们歇一波，后面会有办法把这个情况处理好~

接着看，现在我们用rows指代要完美地发几轮糖果，kids代表包含所有小朋友的列表，那么我们可以算出，第i个小朋友(i从1开始)总共得到了多少糖果，算法如下：
$$
kids[i]=i+(i+n)+(i+2n)+\ldots(i+(\text { rows }-1)* n)
$$
举个例子，如果一共有3个小朋友，那么第1位小朋友总共得到的糖果数量就是：
$$
kids[1]=1+(1+3)+(1+2*3)+\ldots(i+(\text { rows }-1) *3)
$$
可以看出这个kids[i]的糖果数量又是一个等差数列求和，可以根据求和公式
$$
\begin{aligned}
S_{n} &=\frac{n}{2}\left(a+a_{n}\right) \
&=\frac{n}{2}[2 a+(n-1) d] \
&=a n+d \cdot \frac{n(n-1)}{2}
\end{aligned}
$$
公式里面的a就是kids中的第一项i，n在公式里面意味着有多少项，就是rows，d就是小朋友的人数n

所以就有：
$$
d[i]=i \times \text { rows }+n \frac{\text { rows }(\text { rows }-1)}{2}
$$
这样我们就能算出每个小朋友的糖果数量啦~

等等，如果p//n中p < n会导致rows直接等于0，这咋整？

答案就是，我们可以用cols = p % n去专门负责只有一行的情况，以及最后一行的情况

显然cols是一个下标，指向最后那个没能拿到完美糖果数量的倒霉孩子，我们对于i < cols的孩子kids[i]，即倒霉孩子之前的幸运宝宝们，直接累加最后一轮的发放数量即可。对于倒霉孩子，剩下的都给他吧~

来，上代码：

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        # 为了方便理解，把num_people赋值给n，即n个小朋友
        n = num_people
        # 套用上面推出来的公式，直接计算可以完整发放糖果的次数p
        p = int((2 * candies + 0.25)**0.5 - 0.5) 
        # 继续套用公式，算出完整发放糖果以后剩余的糖果数量
        R = int(candies - (p + 1) * p * 0.5)
        # 迭代rows轮，cols是倒霉孩子的下标
        rows, cols = p // n, p % n
        
        # 小朋友们端好了碗，等你发糖
        kids = [0] * n
        for i in range(n):
            # 性感coder，在线发糖
            kids[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n
            # 最后一轮or在p<n时的第一轮
            if i < cols:
                kids[i] += i + 1 + rows * n
        # 最后的那个倒霉孩子开心的拿到了R颗糖       
        kids[cols] += R
        return kids

统计信息

通过次数	提交次数	AC比率
36344	57012	63.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途