↓Skip to main content
  1. Posts/

LeetCode-2929 给小朋友们分糖果 II

·1 min·
Table of Contents

LeetCode-2929 给小朋友们分糖果 II #

Solution 1 #

直接枚举给第一个小朋友的糖果数 $x$ . 如果 $n - x <= 2limit$ , 那么第二个小朋友应该至少分到 $\max(n - x - limit, 0)$ 个. 计算合法的数量即可. 代码如下:

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        ans = 0
        for i in range(min(limit, n), -1, -1):
            if n - i > limit * 2:
                break
            ans += min(n - i, limit) - max(0, n - i - limit) + 1
        return ans

Solution 2 #

使用容斥原理.

代码如下:

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        def cal(x):
            if x < 0:
                return 0
            return x * (x - 1) // 2

        return cal(n + 2) - 3 * cal(n - limit + 1) + 3 * cal(n - (limit + 1) * 2 + 2) - cal(n - 3 * (limit + 1) + 2)