LeetCode 2226. Maximum Candies Allocated to K Children

[Woodyiiiiiii]

Binary-search

class Solution {
    public int maximumCandies(int[] candies, long k) {
        
        long sum = 0;
        long ans = 0;
        
        for (int candy : candies) {
            sum += candy;
        }
        if (sum < k) {
            return (int)ans;
        }
        
        long l = 1, r = sum;
        while (l <= r) {
            long mid = l + (r - l) / 2;
            if (check(candies, mid, k)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        return (int)ans;
        
    }
    
    private boolean check(int[] candies, long limit, long k) {
        for (int candy : candies) {
            if (candy < limit) {
                continue;
            } else {
                k -= candy / limit;
            }
        }
        return k <= 0;
    }
    
}

时隔一年多巩固二分类型题目时再写了这道题：

class Solution {
    public int maximumCandies(int[] candies, long k) {
        long lo = 0, hi = (long) (1e7 + 1);
        while (lo < hi) {
            long mid = (lo + hi) >> 1;
            if (check(candies, k, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return (int) (lo - 1);
    }

    // distribute k children with target number of candies
    private boolean check(int[] candies, long k, long target) {
        long cnt = 0;
        if (target == 0) {
            return true;
        }
        for (int candy : candies) {
            cnt += candy / target;
            if (cnt >= k) {
                return true;
            }
        }
        return cnt >= k;
    }
}

有两个小tips:

1. cnt变量用long才过了
2. 发现最近时不时要用/或者%作为数学计算
3. 二分最难的模块还是check函数

类似题目：

• Leetcode 2517. Maximum Tastiness of Candy Basket #164

---

• 2226. Maximum Candies Allocated to K Children