Loading... > https://leetcode.cn/problems/distribute-candies-to-people/?envType=daily-question&envId=2024-05-02 每分一个小朋友，下个小朋友就多分到一颗糖果，那么分 $n$ 次就可以分出去 $\frac{n (n + 1)}{2}$ 颗糖果。总共有 $candies$ 颗糖果，所以有 $\lfloor\frac{-1 + \sqrt{1 + 8 \times candies}}{2} \rfloor$ 次完整的分配，最后一次只能分到剩余的糖果。 易知每个小朋友每轮获得的糖果数相比上一轮都多出了 $num\_people$ 。假设第 $i$ 个小朋友被分配了 $turn$ 轮，那么该小朋友得到的糖果数为 $i \times turn + \frac{turn \times (taurn - 1)}{2} \times num\_people$ 。注意特判一下最后一轮不完整的分配。 因此代码如下： ```c++ class Solution { public: std::vector<int> distributeCandies(int candies, int num_people) { int n = (int)((sqrt(8.0 * (double)candies + 1.0) - 1.0) / 2.0); int turn = n / num_people, modulus = n % num_people; std::vector<int> res(num_people); for (int i = 0; i < num_people; i++) { if (i == modulus) res[i] = (i + 1) * turn + turn * (turn - 1) * num_people / 2 - n * (n + 1) / 2 + candies; else if (i < modulus) res[i] = (i + 1) * (turn + 1) + turn * (turn + 1) * num_people / 2; else res[i] = (i + 1) * turn + turn * (turn - 1) * num_people / 2; } return res; } }; ``` - 时间复杂度：$O(1)$ 。 - 空间复杂度：$O(1)$ ，除了结果以外不需要额外的空间。 最后修改：2024 年 06 月 03 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏