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;

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.