LeetCode 2226. Maximum Candies Allocated to K Children(2025/3/14 每日一题)

标题：Maximum Candies Allocated to K Children

题目：

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

题目解析：这道题不太好读懂（英文水平有限又死活不肯读中文题的倔强公主读题都读了好几遍）。有一些成捆的蜡烛，分给K个人，分给每个人的时候只能从一捆中拿，不能混合着分。但一大捆可以同时分给几个人。最后要求每个人分的蜡烛数相等，问最多分给每个人几支蜡烛。

这个题读完可以看出，给定一个值N判断能不能分给每人N支好判断，但直接得出这个最大的N很难，因此可以通过不停的判断N来得到这个最大N值。但每次+1肯定是不现实的，因为数据规模很大，candies.length * candies[i] 是1e(12)次方级别的。自然想到用二分法来找这个最大N值。用二分法首先要确定最小值和最大值：

• 最小值，也就是left初始值为1，如果蜡烛总数小于k值，肯定不够分，则返回0. 如果蜡烛总是大于k，那么最少能分给每人1支蜡烛，因为任何数都被1整除。
• 最大值，也就是right初始值为：蜡烛总数 / k。因为最大也不可能超过这个值。
• 为优化时间，公主还做了些截断操作

代码如下：

class Solution {
public:

    // 判断是否能分给每个人mid支蜡烛
    bool isDivided(vector<int>& candies, int mid, long long k){
        for(auto n : candies) {
            k -= n / (long long)mid;
            if (k <= 0) return true;
        }
        return false;
    }

    int maximumCandies(vector<int>& candies, long long k) {
        long long sum = 0;
        for (auto n : candies) {
            sum += (long long) n;
        }
        if (sum < k) return 0;
        if (sum > k && sum < 2*k) return 1; //为优化时间做的截断操作

        //二分法找到最大值
        int avg = (int)(sum / k);
        int left = 1, right = avg;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if (isDivided(candies, mid, k)) {
                left = mid + 1;
            } else right = mid - 1;
        }
        if (isDivided(candies, right, k)) return right;
        return left; 
    }
};

结果：时间复杂度最坏为：O(N*log(N)) 空间复杂度为：O(1)