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符合如下不等式：

\(

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

\)

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

import java.util.Arrays;

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]
    }
}