货运代理网站模板,discuz应用中心破解,中铁建设集团有限公司中标项目,wordpress 首行缩进给你两个正整数 n 和 limit 。
请你将 n 颗糖果分给 3 位小朋友#xff0c;确保没有任何小朋友得到超过 limit 颗糖果#xff0c;请你返回满足此条件下的 总方案数 。 示例 1#xff1a;
输入#xff1a;n 5, limit 2
输出#xff1a;3
解释#xff1a;总共有 3 种方…给你两个正整数 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) 。
解析
正难则反我们先算出总方案数在减去不合法的数即可。
有组合数学可以用隔板法进行求出总方案数。Cn2,2
在考虑不合法的数。
由容斥原理得
考虑到三种情况这里要注意至少这个词语的理解
1.当至少一个人不合法那个人至少要limit1个球在用隔板法在n-limit-1中经行分配 3*Cn- limit-12,2,由题意知道由三个人。
2.当至少有两个人不合法时至少要消耗(limit1)*2个球分配的方案数为3⋅C(n−2⋅(limit1)2,2)
3.至少有三个人不合法时分配的方案数为C(n−3⋅(limit1)2,2
最后总方案数 - 不合法方案数即可。
在上面三种情况中有一些是重复被减去 所以后面要加上。
class Solution {
public:long long c2(long long n){return n 1 ?n*(n-1)/2:0;}long long distributeCandies(int n, int limit) {return c2(n2) - 3*c2(n-limit1) 3*c2(n-2 *limit) - c2(n-3*limit - 1);}
};
