2929.给小朋友们分糖果II

目标

给你两个正整数 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 位小朋友,每个小朋友分到的糖果数量不超过 limit,求分配的方案数。注意,糖果必须分完,比如示例 1,不存在分得糖果数量为 0 的情况。

  • 第一个小朋友分到的糖果数为 a ∈ [0, Math.min(n, limit)]
  • 第二个小朋友分到的糖果数为 b ∈ [Math.max(0, n - a - limit), Math.min(n - a, limit)]
  • 第三个小朋友分到的糖果数为 n - a - b

代码


/**
 * @date 2025-06-01 21:49
 */
public class DistributeCandies2929 {

    public long distributeCandies(int n, int limit) {
        long res = 0L;
        for (int i = 0; i <= Math.min(n, limit); i++) {
            if (n - i > 2 * limit) {
                continue;
            }
            res += Math.min(n - i, limit) - Math.max(0, n - i - limit) + 1;
        }
        return res;
    }
}

性能

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注