怎样建设游戏网站,八爪鱼采集器WordPress接口,网络营销怎么做好推广,做个app需要多少费用3妹#xff1a;1 8得8#xff0c;2 816#xff0c; 3 8妇女节… 2哥 : 3妹#xff0c;在干嘛呢 3妹#xff1a;双11不是过了嘛#xff0c; 我看看我这个双十一买了多少钱#xff0c; 省了多少钱。 2哥 : 我可是一分钱没买。 3妹#xff1a;我买了不少东西#xff0c; …
3妹1 8得82 816 3 8妇女节… 2哥 : 3妹在干嘛呢 3妹双11不是过了嘛 我看看我这个双十一买了多少钱 省了多少钱。 2哥 : 我可是一分钱没买。 3妹我买了不少东西 衣服、包包、化妆器…… 接下来的一个月只能吃土了 还要2哥救助~ 2哥你没有用花呗或信用卡吗 把支付方式重新排列一下 用最晚还款的那种信用卡这样就可以暂时不用吃土啦。 3妹可是后面还是要还信用卡啊。哎 天下要有免费的午餐该有多好啊 2哥 : 傻啊你 后面就发工资了啊 不就缓解了 3妹咦有道理啊 2哥说到免费的午餐我今天看天一个免费的糖果的题目我们来做一下吧~ 题目
给你两个正整数 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 10^6 1 limit 10^6
思路 双指针 n个糖果分给3个小朋友考虑分给第一个小朋友i个糖果那么i的取值范围是[0, min(limit, range)], 此时还剩下left n - i 个糖果分给2个小朋友。 考虑left分成两份位 j 和 left-j 每份的取值范围都需要满足要求。分三种情况 left 2limit, 此时无法满足条件。 left limit, 此时 j取[0, limit]均可有limit1种方法 left limit 且 left/2 limit, 这个时候因为两个人是对称的只需考虑第一个人的取值范围也就是[n-limit, limit]共limit-(n-limit) 1 2limit - n 1种 所以枚举i, 然后对left分情况讨论一次遍历拿到结果。
java代码
class Solution {public long distributeCandies(int n, int limit) {return c2(n 2) - 3 * c2(n - limit 1) 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1);}private long c2(int n) {return n 1 ? (long) n * (n - 1) / 2 : 0;}
}
