题目描述

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个人。

给第一个人 1 颗糖果，第二个人 2 颗，依此类推，直到给最后一个人 n 颗糖果。

然后，我们再回到队伍的起点，给第一个人 n + 1 颗糖果，第二个人 n + 2 颗，依此类推，直到给最后一个人 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的人。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况。

样例

输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。

提示

• 1 <= candies <= 10^9
• 1 <= num_people <= 1000

算法1

(暴力模拟) $O(\sqrt{candies})$

1. 暴力模拟糖果分发过程，由于每次分发的糖果个数都会多 1，根据等差数列求和公式，分发的次数不会超过 $O(\sqrt{candies})$ 次。

时间复杂度

• 如上所述，时间复杂度为 $O(\sqrt{candies})$。

空间复杂度

• 答案需要额外空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> res(num_people, 0);
        int cur = 1;
        while (candies > 0) {
            for (int i = 0; i < num_people; i++) {
                if (candies >= cur) {
                    res[i] += cur;
                    candies -= cur;
                } else {
                    res[i] += candies;
                    candies = 0;
                    break;
                }
                cur++;
            }
        }
        return res;
    }
};

算法2

(数学) $O(n)$

1. 根据 candies 算出一共可以完整的分发多少轮糖果 m。根据等差数列求和公式，完整的分发轮数应该在 (int)sqrt(candies) 或者 (int)sqrt(candies) - 1 中的某一个。
2. 求出最后一次分发可以分出的糖果数为 leftover = candies - m * (m + 1) / 2。
3. 遍历一遍 people 进行分发（下标从 0 开始）。假设当前给第 i 个人分发糖果，则先求出能完整给他分发的次数为 t = m / num_people + x，其中如果 i < m % num_peopel，则 x = 1；否则 x = 0。
4. 计算具体分发的糖果数为 (i + 1) * t + t * (t - 1) / 2 * num_people，这里的计算就是等差数列求和 i + (n + i) + (2n + i) + ... + (tn + i)。
5. 最后，第 m % num_people 个人加上 leftover 个糖果。

时间复杂度

• 仅遍历 people 一次，故时间复杂度为 $O(n)$。

空间复杂度

• 答案需要额外空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> res(num_people, 0);
        int m = sqrt(candies * 2);
        int leftover;

        if ((long long)(m) * (m + 1) / 2 > candies)
            m--;

        leftover = candies - m * (m + 1) / 2;

        for (int i = 0; i < num_people; i++) {
            int t = m / num_people + (int)(i < m % num_people);
            res[i] = (i + 1) * t + t * (t - 1) / 2 * num_people;
        }

        res[m % num_people] += leftover;

        return res;
    }
};