跳转至

2928. 给小朋友们分糖果 I

题目描述

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友,确保没有任何小朋友得到超过 limit 颗糖果,请你返回满足此条件下的 总方案数 。

 

示例 1:

输入:n = 5, limit = 2
输出:3
解释:总共有 3 种方法分配 5 颗糖果,且每位小朋友的糖果数不超过 2 :(1, 2, 2) ,(2, 1, 2) 和 (2, 2, 1) 。

示例 2:

输入:n = 3, limit = 3
输出:10
解释:总共有 10 种方法分配 3 颗糖果,且每位小朋友的糖果数不超过 3 :(0, 0, 3) ,(0, 1, 2) ,(0, 2, 1) ,(0, 3, 0) ,(1, 0, 2) ,(1, 1, 1) ,(1, 2, 0) ,(2, 0, 1) ,(2, 1, 0) 和 (3, 0, 0) 。

 

提示:

  • 1 <= n <= 50
  • 1 <= limit <= 50

解法

方法一:组合数学 + 容斥原理

根据题目描述,我们需要将 $n$ 个糖果分给 $3$ 个小孩,每个小孩分到的糖果数在 $[0, limit]$ 之间。

这实际上等价于把 $n$ 个球放入 $3$ 个盒子中。由于盒子可以为空,我们可以再增加 $3$ 个虚拟球,然后再利用隔板法,即一共有 $n + 3$ 个球,我们在其中 $n + 3 - 1$ 个位置插入 $2$ 个隔板,从而将实际的 $n$ 个球分成 $3$ 组,并且允许盒子为空,因此初始方案数为 $C_{n + 2}^2$。

我们需要在这些方案中,排除掉存在盒子分到的小球数超过 $limit$ 的方案。考虑其中有一个盒子分到的小球数超过 $limit$,那么剩下的球(包括虚拟球)最多有 $n + 3 - (limit + 1) = n - limit + 2$ 个,位置数为 $n - limit + 1$,因此方案数为 $C_{n - limit + 1}^2$。由于存在 $3$ 个盒子,因此这样的方案数为 $3 \times C_{n - limit + 1}^2$。这样子算,我们会多排除掉同时存在两个盒子分到的小球数超过 $limit$ 的方案,因此我们需要再加上这样的方案数,即 $3 \times C_{n - 2 \times limit}^2$。

时间复杂度 $O(1)$,空间复杂度 $O(1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        if n > 3 * limit:
            return 0
        ans = comb(n + 2, 2)
        if n > limit:
            ans -= 3 * comb(n - limit + 1, 2)
        if n - 2 >= 2 * limit:
            ans += 3 * comb(n - 2 * limit, 2)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int distributeCandies(int n, int limit) {
        if (n > 3 * limit) {
            return 0;
        }
        long ans = comb2(n + 2);
        if (n > limit) {
            ans -= 3 * comb2(n - limit + 1);
        }
        if (n - 2 >= 2 * limit) {
            ans += 3 * comb2(n - 2 * limit);
        }
        return (int) ans;
    }

    private long comb2(int n) {
        return 1L * n * (n - 1) / 2;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int distributeCandies(int n, int limit) {
        auto comb2 = [](int n) {
            return 1LL * n * (n - 1) / 2;
        };
        if (n > 3 * limit) {
            return 0;
        }
        long long ans = comb2(n + 2);
        if (n > limit) {
            ans -= 3 * comb2(n - limit + 1);
        }
        if (n - 2 >= 2 * limit) {
            ans += 3 * comb2(n - 2 * limit);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func distributeCandies(n int, limit int) int {
    comb2 := func(n int) int {
        return n * (n - 1) / 2
    }
    if n > 3*limit {
        return 0
    }
    ans := comb2(n + 2)
    if n > limit {
        ans -= 3 * comb2(n-limit+1)
    }
    if n-2 >= 2*limit {
        ans += 3 * comb2(n-2*limit)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function distributeCandies(n: number, limit: number): number {
    const comb2 = (n: number) => (n * (n - 1)) / 2;
    if (n > 3 * limit) {
        return 0;
    }
    let ans = comb2(n + 2);
    if (n > limit) {
        ans -= 3 * comb2(n - limit + 1);
    }
    if (n - 2 >= 2 * limit) {
        ans += 3 * comb2(n - 2 * limit);
    }
    return ans;
}

评论