给小朋友们分糖果 I
难度:
标签:
题目描述
You are given two positive integers n
and limit
.
Return the total number of ways to distribute n
candies among 3
children such that no child gets more than limit
candies.
Example 1:
Input: n = 5, limit = 2 Output: 3 Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).
Example 2:
Input: n = 3, limit = 3 Output: 10 Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (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) and (3, 0, 0).
Constraints:
1 <= n <= 50
1 <= limit <= 50
代码结果
运行时间: 22 ms, 内存: 15.9 MB
/*
* Problem: Given two positive integers n and limit, you need to distribute n candies among 3 children such that no child receives more than limit candies. Return the total number of ways to do so.
*
* Approach: Use Java Streams to generate all possible combinations of distributing candies to three children. Filter out the combinations where any child gets more than limit candies, and then count the valid combinations.
*/
import java.util.stream.IntStream;
public class CandyDistributionStream {
public static int countWays(int n, int limit) {
return (int) IntStream.rangeClosed(0, Math.min(n, limit))
.boxed()
.flatMap(i -> IntStream.rangeClosed(0, Math.min(n - i, limit))
.mapToObj(j -> new int[]{i, j, n - i - j}))
.filter(arr -> arr[2] <= limit)
.count();
}
public static void main(String[] args) {
int n = 5;
int limit = 2;
System.out.println(countWays(n, limit)); // Output: 3
}
}
解释
方法:
该题解使用了组合数学中的Stars and Bars定理来解决分糖果问题。Stars and Bars定理用于计算将n个相同的物体分配到k个不同的箱子中的方式数。在本题中,我们需要将n颗糖果分给3个小朋友,并满足每位小朋友的糖果数不超过limit。首先,计算不考虑限制的分配方法数,然后使用容斥原理(Inclusion-Exclusion Principle)来去除那些违反条件的分配情况。具体来说,先计算所有可能的分配方法数,再减去至少有一位小朋友得到超过limit颗糖果的情况,然后加上至少有两位小朋友得到超过limit的情况,最后减去所有三位小朋友都得到超过limit颗糖果的情况。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在计算至少有一个小朋友得到超过limit颗糖果的情况时,使用的公式是`3 * C2(n + 2 - (limit + 1))`?这里的`3`和`(limit + 1)`是如何确定的?
▷🦆
Stars and Bars定理在这种有限制条件的情况下是如何应用的?请解释如何从无限制情况转化到有限制情况。
▷🦆
在使用容斥原理计算时,如何确保`n + 2 - k * (limit + 1)`(其中k为1, 2, 3)的值非负,这对于解题有什么限制或影响?
▷🦆
在题解中提到的`C2`函数是如何确保正确计算组合数的,特别是当输入的n小于2时?
▷