1103. 分糖果 II

ゝ一世哀愁。 2023-10-04 18:52 44阅读 0赞

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num\_people 个小朋友。

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

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

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

返回一个长度为 num\_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans\[i\] 表示第 i 个小朋友分到的糖果数）。

示例 1：

输入：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\]。  
示例 2：

输入：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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/distribute-candies-to-people  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：暴力  
思路

最直观的方法是不断地遍历数组，如果还有糖就一直分，直到没有糖为止。

Python3JavaC++

class Solution:  
def distributeCandies(self, candies: int, num\_people: int) -> List\[int\]:  
ans = \[0\] \* num\_people  
i = 0  
while candies != 0:  
ans\[i % num\_people\] += min(i + 1, candies)  
candies -= min(i + 1, candies)  
i += 1  
return ans  
复杂度分析

空间复杂度：\\mathcal\{O\}(1)O(1)，除了答案数组只需要常数空间来存储若干变量。

方法二：等差数列求和  
思路

这是一个数学问题，可以对其简化。

更好的做法是使用一个简单的公式代表糖果分配，可以在 \\mathcal\{O\}(N)O(N) 时间内完成糖果分发，并生成最终的分配数组。

接下来逐步推导该公式。

获得完整礼物的人数

除了最后一份礼物数量由剩余糖果数量决定以外，其他礼物的数量都是从 1 开始构成的等差数列。

假设数列一共有 p 个元素，剩余的糖果就是糖果数量 CC 与等差数列前 pp 项之差。

不完整分发礼物的回合

最后一个回合可能不完整，因为有可能只是一部分人收到了礼物。

在最后一个回合中，可以计算出收到完整礼物的人数 cols = p % N。这些人比其他人多获得一份完整的礼物。

d\[i\] += i + N \\times \\textrm\{rows\}  
d\[i\]+=i+N×rows

最后一位拥有礼物的人获得所有剩余的糖果。

d\[\\textrm\{cols\} + 1\] += \\textrm\{remaining\}  
d\[cols+1\]+=remaining

这就是分发所有糖果的过程。

算法

计算完整礼物的份数

最后一份礼物的糖果数量

\\textrm\{remaining\} = C - \\frac\{p(p + 1)\}\{2\}  
remaining=C−  
2  
p(p+1)

完整的分发回合数：rows = p // n。此时每个人拥有的礼物数量：

d\[i\] = i \\times \\textrm\{rows\} + N \\frac\{\\textrm\{rows\}(\\textrm\{rows\} - 1)\}\{2\}  
d\[i\]=i×rows+N  
2  
rows(rows−1)

前 p % N 个人最后再获得一份完整的礼物：d\[i\] += i + N \\times \\textrm\{rows\}d\[i\]+=i+N×rows。

将剩余的糖果分发给第 p % N 个后面的一个人。

返回糖果分配数组：d。

class Solution {
        public int[] distributeCandies(int candies, int num_people) {
            int n = num_people;
            // how many people received complete gifts
            int p = (int) (Math.sqrt(2 * candies + 0.25) - 0.5);
            int remaining = (int)(candies - (p + 1) * p * 0.5);
            int rows = p / n, cols = p % n;
    
            int[] d = new int[n];
            for (int i = 0; i < n; ++i) {
                // complete rows
                d[i] = (i + 1) * rows + (int)(rows * (rows - 1) * 0.5) * n;
                // cols in the last row
                if (i < cols) {
                    d[i] += i + 1 + rows * n;
                }
            }
            // remaining candies        
            d[cols] += remaining;
            return d;
        }
    }
    
    作者：LeetCode-Solution
    链接：https://leetcode.cn/problems/distribute-candies-to-people/solution/fen-tang-guo-ii-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#### 解题思路 ####

二分找到num，然后利用等差数列求和公式，计算出剩余糖果数，然后遍历num\_people，填充答案！

class Solution {
        public static int[] distributeCandies(int candies, int num_people) {
            if (num_people <= 0) {
                return new int[]{};
            }
    
            int[] res = new int[num_people];
            int num = binarySearch(candies);
            int rounds = num / num_people;
            int remain = candies - getSum(1, rounds * num_people, rounds * num_people);
    
            for (int i = 1; i <= num_people; i++) {
                int total =  getSum(i, i + (rounds - 1) * num_people, rounds);
                if (remain > 0) {
                    total += Math.min(remain, i + rounds * num_people);
                    remain -= Math.min(remain, i + rounds * num_people);
                }
                res[i - 1] = total;
            }
    
            return res;
        }
    
        // 等差数列公式
        public static int getSum(int a1, int an, int n) {
            return (a1 + an) * n / 2;
        }
    
        // 二分查找
        private static int binarySearch(int candies) {
            int left = 0;
            int right = candies;
            int ans = 0;
            while (left <= right) {
                // 2147483647
                // 1000000000
                int mid = (left + right) / 2;
                long total = mid * (mid + 1l) / 2;
                if (total < candies) {
                    ans = mid;
                    left = mid + 1;
                } else if (total > candies) {
                    right = mid - 1;
                } else {
                    ans = mid;
                    break;
                }
            }
            return ans;
        }
    }
    
    作者：jue-ban-nan-zi
    链接：https://leetcode.cn/problems/distribute-candies-to-people/solution/by-jue-ban-nan-zi-kppf/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。