Loading... > https://leetcode.cn/problems/distribute-candies-among-children-i/description/?envType=daily-question&envId=2024-05-02 该问题相当于 $n$ 个糖果排成一行，并在中间插入两个挡板，因此有 $C_{n+2}^2$ 种方案。但题目限制每个小孩拿到的糖果不能超过 `limit` ，所以需要减去不合法的方案。 假设至少一个小朋友分到的糖果超过了 `limit` ，那么我们可以先分给该小朋友 `limit + 1` 颗糖果，然后再将剩余的糖果分给所有人。这样的话就有 $C_{n - (limit + 1) + 2}^2$ 个方案。对剩下两个小朋友也做相同的分配法，最后得到的方案数为 $3 \times C_{n - (limit + 1) + 2}^2$ 。 但这样的话就会重复统计 "至少两个小朋友分到的糖果超过了 `limit`" 的情况，需要减去多统计的部分。 假设又两个小朋友分到的糖果超过了 `limit` ，那么先给他们各分 `limit + 1` 颗糖果，然后再将剩余的糖果分配给所有人。这样就有 $C_{n - 2 \cdot (limit + 1) + 2}^2$ 种分配方案。三个小朋友中选两个有 3 种方案，所以最终方案数为 $3 \times C_{n - 2 \cdot (limit + 1) + 2}^2$ 。 直接相减的话会把 "三个小朋友分到的糖果都超过了 `limit`" 这种情况给减去，所以需要加回来。 按照之前的思想，先给每个小朋友分 $limit + 1$ 颗糖果，然后再将剩余的糖果分配给所有人，这样就有 $C_{n - 3 \cdot (limit + 1) + 2}^2$ 种方案。 因此最终的答案应该是： $$ C_{n+2}^2 - 3 C_{n - limit + 1}^2 + 3 C_{n - 2 \cdot limit}^2 - C_{n - 3 \cdot limit - 1}^2 $$ ```c++ class Solution { int c2(int n) { return n > 1 ? n * (n - 1) / 2 : 0; } public: int distributeCandies(int n, int limit) { return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1); } }; ``` - 时间复杂度：$O(1)$ 。 - 空间复杂度：$O(1)$ 。 最后修改：2024 年 06 月 01 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏