难度: Hard
Submission
运行时间: 36 ms
内存: 16.8 MB
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
def c2(n):
if n <= 1:
return 0
return n * (n-1) // 2
# 容斥原理
# 所有方案数
# 三个朋友都分到limit+1以上个, 剩下的分配到3人
n3 = c2(n - 3 * (limit + 1) + 2)
# 至少两个朋友分到limit + 1 以上
n2 = c2(n - 2 * (limit + 1) + 2)
# 至少一个朋友分到limit + 1 以上
n1 = c2(n - 1 * (limit + 1) + 2)
return c2(n+2) - (3 * n1 - 3 * n2 + n3)
Explain
该题解采用容斥原理来解决分糖果问题。给定n个糖果和每个小朋友最多能分到的糖果数limit，问题可以转化为计算特定条件下的组合问题。首先定义一个辅助函数c2(n)，用于计算从n个糖果中任意分配给三个小朋友的方式（即组合数C(n+2, 2)）。容斥原理用于从全集中减去不符合条件的部分。计算分步如下： 1. n1: 至少一个朋友分到超过limit的糖果数。 2. n2: 至少两个朋友分到超过limit的糖果数。 3. n3: 三个朋友都分到超过limit的糖果数。 最终的有效分配方式为所有可能的分配方式减去不符合条件的分配方式，通过容斥原理计算得到。
时间复杂度: O(1)
空间复杂度: O(1)
# 定义Solution类
class Solution:
# 定义分发糖果的函数
def distributeCandies(self, n: int, limit: int) -> int:
# 定义辅助函数c2，计算组合数C(n+2, 2)
def c2(n):
# 如果n <= 1，没有有效的分配方式
if n <= 1:
return 0
# 计算并返回组合数
return n * (n-1) // 2
# 应用容斥原理，计算不同情况下的组合数
# 计算三个朋友至少都分到limit+1个糖果的情况
n3 = c2(n - 3 * (limit + 1) + 2)
# 计算至少两个朋友分到limit+1个糖果的情况
n2 = c2(n - 2 * (limit + 1) + 2)
# 计算至少一个朋友分到limit+1个糖果的情况
n1 = c2(n - 1 * (limit + 1) + 2)
# 使用容斥原理得出最终结果
return c2(n+2) - (3 * n1 - 3 * n2 + n3)
Explore
在这个问题中，`C(n+2, 2)`的计算公式用于表示从n个糖果中分配给三个小朋友的所有可能方式。由于每个小朋友可以分到0到多个糖果，这可以看作是一个将n个相同的糖果放入三个不同的盒子（每个盒子代表一个小朋友）的问题。在组合数学中，这种问题可以通过添加两个虚拟糖果（代表将糖果分割成三份的分割点）来转换为从n+2个项目中选择2个项目的组合问题，即`C(n+2, 2)`。这样计算的结果就代表了将n个糖果分给三个小朋友的所有可能分配方法。
在计算n1, n2, n3时，将limit加1是为了确保至少有一个小朋友分到超过limit个糖果。例如，如果limit是每个小朋友最多能分到的糖果数，那么limit+1就是小朋友分到超过limit的最小糖果数。将这个数乘以小朋友的数量后从n中减去，是为了计算在至少有1个（对于n1）、2个（对于n2）、3个（对于n3）小朋友分到超过limit个糖果的情况下，剩余的糖果数。这样，我们就能计算这些边界情况下的有效分配方法。
在计算n1, n2, n3的组合数时，参数中的`+2`是为了将问题转换为组合问题。`n - k * (limit + 1)`计算的是在至少k个小朋友分到超过limit个糖果后剩余的糖果数。而`+2`则是为了将这些剩余的糖果分配给3个小朋友，这与之前解释的`C(n+2, 2)`相同，即将n个糖果分为三部分的组合问题。通过这种方式，我们可以计算在给定至少有k个小朋友超过limit的情况下，剩余糖果的分配方法。