LeetCode 1103：Distribute Candies to People

本文为LeetCode 1103：Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果：

我们给第一个人1块糖，给第二个人2块糖，以此类推，直到我们给最后一个人n块糖。

然后，我们回到开始，给第一个人n + 1块糖，给第二个人n + 2块糖，以此类推，直到我们给最后一个人2 * n块糖。

这个过程不断重复（当重新走到队首的时候，我们每次比上次多给n个糖果），直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组（长度为num_people），该数组表示最终每个人得到的糖果数量。

题解

首先我们考虑能完整的分发几轮。

由于分发数量总体上就是从1到n*num_people的等差序列，n符合如下不等式：

[latex] \sum_{i=1}^{n*num\_people}i \leq candies \rightarrow n \leq \frac{\sqrt{2*candies+\frac{1}{4}}-\frac{1}{2}}{num\_people} [/latex]

然后对于剩下的，进行一次分发即可：

import java.util.Arrays;

/**
* https://www.robberphex.com/distribute-candies-to-people/
*/
class Solution {

public int\[\] distributeCandies(int candies, int num\_people) {
    int\[\] result = new int\[num\_people\];

    // 能进行完整分配的次数
    int completeRound = (int) ((Math.sqrt(2 \* candies + 1 / 4.) - 1 / 2.) / num\_people);
    // 分配
    for (int i = 0; i < num\_people; i++) {
        result\[i\] = completeRound \* (i + 1) + (completeRound - 1) \* completeRound \* num\_people / 2;
    }
    // 减掉分配过的
    candies -= (1 + completeRound \* num\_people) \* completeRound \* num\_people / 2;

    // 开始最后一轮分配
    for (int i = 0; i < num\_people && candies > 0; i++) {
        int giveCandie = completeRound \* num\_people + i + 1;
        if (candies < giveCandie) {
            giveCandie = candies;
        }
        result\[i\] += giveCandie;
        candies -= giveCandie;
    }


    return result;
}

public static void main(String\[\] args) {
    int\[\] res = new Solution().distributeCandies(10, 3);
    System.out.println(Arrays.toString(res));
    // 输出 \[5, 2, 3\]
}

}