企业官网建设流程全解析

• 科学计算

本文围绕 LeetCode 第 287 场周赛 T3「Maximum Candies Allocated to K Children」（分糖果给 k 个小孩，题解文档见 leetcode/weekly/287/c/2226.md），系统讲解如何用二分答案解决"最大化最小值"类问题。你将从"能否让每个小孩都至少有 low 颗糖果"的单调性判定出发，掌握判定函数 check 的推导、开区间二分端点选取与上界优化技巧，并结合本仓库的 Go 实现 c.go 与测试用例 c_test.go，看懂sort.Search的取反技巧在"最大化最小值"场景下的应用。

问题背景：把糖果分给 k 个小孩

题面（weekly 287 第三题题解）：给定一个长度为 $n$ 的数组candies，其中candies[i]表示第 $i$ 堆糖果的数量。现在要把糖果分给 $k$ 个小孩，要求每个小孩恰好得到相同数量的糖果；糖果堆只能分割、不能合并（即可以从一堆中切出任意数量给若干小孩，但不能把两堆拼在一起）。求每个小孩最多能拿到多少颗糖果；若无法分配，返回 $0$。

从仓库中题解与实现代码的函数签名可以看出，本题的 $k$ 使用 64 位整数（Java 的long k、Go 的k int64），累加过程也需要注意使用足够宽的整数类型：

// leetcode/weekly/287/c/c.go func maximumCandies(candies []int, k int64) int

对应测试用例（c.txt）也非常直观：

• 输入candies = [5,8,6]、k = 3，答案为5（可以切出三堆大小为 5 的糖果，剩余部分丢弃）；
• 输入candies = [2,5]、k = 11，答案为0（糖果总数只有 7 颗，少于 11 个小孩，无法满足"每人至少 1 颗"，返回 0）。

核心思路：从"最大化最小值"到"二分答案"

这个问题不是问"最多能分多少"，而是等价于"每个小孩至少分到 $\textit{low}$ 颗时，能否让所有小孩都满足"。于是先考虑一个判定型子问题：

能否让每个小孩都至少有 $\textit{low}$ 颗糖果？

关键观察是单调性：$\textit{low}$ 越大，越难实现；$\textit{low}$ 越小，越容易实现。例如当 $\textit{low}=5$ 时可以满足要求，而 $\textit{low}=6$ 时无法满足，那么答案就是 $5$。具有这种单调性的问题，就可以二分猜答案——这就是"二分答案"算法的适用前提（该思路在竞赛界常配合"红蓝染色法"理解：满足条件的一端涂一种颜色，不满足的一端涂另一种颜色，答案就是红蓝分界点）。

因为糖果堆只能分割不能合并，对于每一堆candies[i]，当每人分 $\textit{low}$ 颗时，最多能分出

$$ c=\left\lfloor\dfrac{\textit{candies}[i]}{\textit{low}}\right\rfloor $$

个大小为 $\textit{low}$ 的糖果堆，即满足 $c$ 个小孩。对全部堆求和，只要

$$ \sum_{i=0}^{n-1} \left\lfloor\dfrac{\textit{candies}[i]}{\textit{low}}\right\rfloor \ge k $$

就说明每个小孩都可以拿到至少 $\textit{low}$ 颗糖果，此时答案还能更大，于是增大二分左边界 $\textit{left}$；否则需要减小右边界 $\textit{right}$。这就是典型的最大化最小值（Maximize the Minimum）二分答案模型，仓库的算法模板 copypasta/sort.go 也把这类题目单列为「最大化最小值（二分下界 low+1…）」一档，本题正是这一模型的标准例题。

二分查找细节：开区间、端点初始化与上界优化

原题解采用开区间二分，即left是"已知满足要求"的答案下界、right是"已知不满足要求"的上界，循环不变量为left < 答案 ≤ right（此处具体写法为left + 1 < right时退出）。这只是一种写法，闭区间或半闭半开区间同样可以，关键是维护好单调性与区间不变量。

三个初始化细节直接决定了二分的正确性与效率：

1. 开区间左端点初始值为 $0$：一颗糖果都不分（每人 0 颗），显然满足"至少有 0 颗"，所以 $0$ 一定是可行解，作为下界；
2. 开区间右端点初始值为 $\max(\textit{candies}) + 1$：由于糖果堆只能分割不能合并，任何小孩拿到超过最大单堆数量的糖果都是不可能的，即 $\max(\textit{candies})$ 一定不可行，加 1 作为上界；
3. 右端点上界优化：设 $\textit{avg} = \left\lfloor\dfrac{\sum_{i} \textit{candies}[i]}{k}\right\rfloor$，因为总量只有这么多，每个小孩均分也不可能超过 $\textit{avg}$，所以 $\textit{avg}+1$ 同样无法满足要求。取 $$ \textit{right} = \min\big(\max(\textit{candies}),\ \textit{avg}\big) + 1 $$ 可以显著缩小二分范围，减少二分次数。这个优化在本仓库 c.go 中体现为min(mx, total/int(k))，也出现在 2226.md 的全部四种语言实现里。

判定函数 check 与多语言实现

判定函数是二分答案的核心：给定候选值low，遍历所有糖果堆累加candies[i] / low，判断总和是否 $\ge k$。一旦累加达到 $k$ 即可提前返回，避免无谓的计算（Java/C++/Go 实现都做了这一剪枝）。

原题解给出了四种语言的完整实现，全部可直接运行：

Python3（手写开区间二分）

class Solution: def maximumCandies(self, candies: List[int], k: int) -> int: def check(low: int) -> bool: return sum(c // low for c in candies) >= k left, right = 0, min(max(candies), sum(candies) // k) + 1 while left + 1 < right: mid = (left + right) // 2 if check(mid): left = mid else: right = mid return left

Python3（库函数bisect_left+key）：把判定改写成"二分最大的不满足要求的low+1，那么答案就是 low"，从而直接复用bisect_left（key=参数需要 Python 3.10+）：

class Solution: def maximumCandies(self, candies: List[int], k: int) -> int: # 二分最大的不满足要求的 low+1，那么答案就是 low def check(low: int) -> bool: low += 1 return sum(c // low for c in candies) < k right = min(max(candies), sum(candies) // k) return bisect_left(range(right), True, key=check)

Java：注意k为long，sum也用long累加并做提前返回：

class Solution { public int maximumCandies(int[] candies, long k) { int mx = 0; long sum = 0; for (int c : candies) { mx = Math.max(mx, c); sum += c; } int left = 0; int right = (int) Math.min(mx, sum / k) + 1; while (left + 1 < right) { int mid = (left + right) >>> 1; if (check(mid, candies, k)) { left = mid; } else { right = mid; } } return left; } private boolean check(int low, int[] candies, long k) { long sum = 0; for (int c : candies) { sum += c / low; if (sum >= k) { // 提前返回 return true; } } return false; } }

C++：同样在 check 内提前返回，并用reduce/ranges::max（C++20）计算总和与最大值：

class Solution { public: int maximumCandies(vector<int>& candies, long long k) { auto check = & -> bool { long long sum = 0; for (int c : candies) { sum += c / low; if (sum >= k) { // 提前返回 return true; } } return false; }; long long avg = reduce(candies.begin(), candies.end(), 0LL) / k; int left = 0, right = min(1LL * ranges::max(candies), avg) + 1; while (left + 1 < right) { int mid = left + (right - left) / 2; (check(mid) ? left : right) = mid; } return left; } };

仓库 Go 实现剖析：sort.Search 的取反技巧

本仓库把该题收录在 leetcode/weekly/287/c/c.go，其实现与题解的 Python 库函数版思路完全一致，但借助 Go 标准库sort.Search完成了"最大化最小值"的经典写法：

package main import "sort" // github.com/EndlessCheng/codeforces-go func maximumCandies(candies []int, k int64) int { mx, total := 0, 0 for _, c := range candies { mx = max(mx, c) total += c } // 二分最大的不满足要求的 low+1，那么答案就是 low return sort.Search(min(mx, total/int(k)), func(low int) bool { low++ sum := 0 for _, candy := range candies { sum += candy / low if sum >= int(k) { // 提前返回 return false } } return true }) }

这里有一个非常值得掌握的技巧，仓库算法模板 copypasta/sort.go 的「最大化最小值」分类下也有同样的注释：

• sort.Search(n, f)返回的是第一个使f(i)为 true 的下标，即"不满足f的最小位置"；
• 本题要求的是"满足sum(c // low) >= k的最大low"，恰好与sort.Search的语义相反。因此把判定函数取反：f(low)表示"每人分low+1颗时无法满足要求（sum < k）"，那么sort.Search找到的第一个"不满足"位置，减 1 就是最大可行值——这正是注释所写的"二分最大的不满足要求的 low+1，那么答案就是 low"；
• low++的写法把开区间二分的"右端点不可行"语义直接映射为f的定义域，配合min(mx, total/int(k))作为搜索长度，整套代码无需手写 while 循环，边界处理非常干净。

这一技巧与bisect_left库函数版是同一思想的两种表达：把"最大化最小值"转成"二分最小不可行值"。

仓库内的测试验证：从生成器到用例文件

这道题的解法在仓库中是有完整测试闭环的：

1. 测试入口leetcode/weekly/287/c/c_test.go 调用testutil.RunLeetCodeFuncWithFile(t, maximumCandies, "c.txt", targetCaseNum)，用 c.txt 中的样例批量验证maximumCandies的输出；
2. 该测试文件头部标注了Code generated by copypasta/template/leetcode/generator_test.go，说明它由 copypasta/template/leetcode/generator_test.go 自动生成——仓库为每道 LeetCode 题提供了统一的"题解 + 用例文件 + 自动测试"工作流；
3. 用例文件 c.txt 按"输入数组 / k / 期望答案"的格式组织（如[5,8,6]、3、5一组），涵盖普通解与返回 0 的退化情形（[2,5]、11、0）。

在仓库根目录执行go test ./leetcode/weekly/287/c/即可运行该题的单测，验证二分实现与题解推导一致。

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log U)$，其中 $n$ 是candies的长度，$U$ 为二分上界初始值（未优化时为 $\max(\textit{candies})$，采用 $\min(\max, \textit{avg})$ 优化后更小）。每次 check 需要遍历一次数组做除法求和；
• 空间复杂度：$\mathcal{O}(1)$，仅使用常数个变量，未申请额外数组。

延伸：二分答案的常见变体与仓库题单

"最大化最小值"只是二分答案的一个分支。本仓库 copypasta/sort.go 开篇的算法题单对该模型做了完整的分类整理，包含：

• 二分答案：求最小 / 求最大：把"可行性判定"嵌入二分，check 通常为贪心或最短路等子过程；
• 最小化最大值（二分上界 upper）：好比"用一个盖子去压住最大值"，check 判断"是否存在方案使所有元素不超过 upper"；
• 最大化最小值（二分下界 low+1）：即本题模型，copypasta/sort.go 同时给出了配套的sort.Search返回语义取反技巧；
• 第 K 小/大、0-1 分数规划、二分间接值、最小化中位数：进阶变体，覆盖 Codeforces/AtCoder/Luogu 等平台的大量题目（如 CF1623C、CF460C、LC 等）。

把一道题抽象为"单调性 + 可快速判定的 check 函数"，再套用对应的二分变体，是处理这类最优化问题的高效通用方法。理解了本题的分割糖果判定，也就掌握了二分答案中最经典的一类骨架。

参考资料（仓库内）

• 题解文档：leetcode/weekly/287/c/2226.md
• Go 题解实现：leetcode/weekly/287/c/c.go
• 测试与用例：leetcode/weekly/287/c/c_test.go、leetcode/weekly/287/c/c.txt
• 二分答案分类题单与sort.Search技巧：copypasta/sort.go
• 周赛题解生成模板：copypasta/template/leetcode/generator_test.go

• 科学计算