分糖果 II

标签: 数学 模拟

难度: Easy

排排坐，分糖果。

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

Submission

运行时间: 25 ms

内存: 16.1 MB

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        ans = [0 for _ in range(num_people)]
        candy_i = 1
        i=0
        while candies > 0:
            ans[i] += candy_i
            candies -= candy_i
            candy_i += 1
            if candy_i > candies:
                candy_i = candies
            i+=1
            if i == num_people:
                i = 0
        return ans

Explain

这个问题的基本思路是模拟分发糖果的过程。我们初始化一个等于num_people长度的列表，用于记录每个小朋友分到的糖果数。然后，我们从第一个小朋友开始，依次给每个小朋友分发越来越多的糖果。每次分发的糖果数量从1开始递增。如果在某一轮中剩余的糖果不足以按计划数量分发，则将剩余的全部糖果分给当前的小朋友。这个过程持续进行，直到所有的糖果都被分发完毕。

时间复杂度: O(sqrt(candies))

空间复杂度: O(num_people)

# 定义分糖果的类和方法

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        ans = [0 for _ in range(num_people)]  # 初始化每个小朋友的糖果数为0
        candy_i = 1  # 开始时给出的糖果数量
        i = 0  # 当前小朋友的索引
        while candies > 0:  # 当还有糖果剩余时执行循环
            ans[i] += candy_i  # 当前小朋友获得candy_i颗糖果
            candies -= candy_i  # 减少总糖果数
            candy_i += 1  # 下一次分发的糖果数增加
            if candy_i > candies:  # 如果剩下的糖果不够下次分发
                candy_i = candies  # 使用剩下的全部糖果作为下次分发量
            i += 1  # 移动到下一个小朋友
            if i == num_people:  # 如果到达最后一个小朋友
                i = 0  # 重新开始从第一个小朋友分发
        return ans  # 返回每个小朋友的糖果分发情况

Explore

在每一轮的循环中，我们通过检查即将分发的糖果数（candy_i）与剩余糖果数（candies）的关系来确保正确处理。如果candy_i大于剩余的candies，我们将candy_i设置为剩余的candies数量，这样当前的小朋友就会得到所有剩余的糖果，然后糖果数归零，循环结束。这种条件判断确保了每一次分发都不会超过剩余糖果的数量。

是的，这种方法可能导致某些小朋友在最后一轮中获得的糖果数远多于其他人，特别是在糖果总数与人数比例不均时更明显。虽然这种分配方法简单且符合规则，但从公平性角度看，它可能导致不均等的结果。在实际应用中，可能需要更复杂的逻辑来确保每个小朋友获得相对公平的糖果数量。

在实际的应用中，num_people为零或负数是不合理的输入，因为它不符合问题的实际场景（即至少需要一个人来分配糖果）。因此，应在程序开始时添加输入验证：如果num_people小于等于0，则应抛出异常或返回一个错误信息，指示输入无效。

当candies数目非常大而num_people相对较小时，分糖果的模拟过程将进行多轮，每个人在每轮中获得的糖果数逐渐增加。这将导致糖果的分配在数量上呈现显著的递增趋势，而且由于分配到最后可能剩余大量糖果，最后几个小朋友可能会获得比其他人多很多的糖果。这种情况下糖果分配的不平等程度可能会更加明显。