1. 项目概述从一道模拟赛题看贪心算法的实战拆解最近在整理过去的算法竞赛题目翻到了这道“书页”题。它来自一场模拟赛标签是“贪心”但实际做下来发现远不止一个“贪”字那么简单。很多刚接触贪心算法的朋友容易陷入一个误区认为贪心就是“每一步都选当前最优的”这没错但关键在于你得先想明白“在当前局面下什么才是‘最优’的定义”。这道“书页”题就是一个绝佳的例子它表面上是一个分配问题但内核却考验着你如何设计合理的“贪心策略”以及如何证明其正确性。今天我就结合这道题把贪心算法的核心思路、策略设计、证明方法以及编码实现中的坑给大家掰开揉碎了讲清楚。无论你是正在备赛的选手还是对算法设计感兴趣的程序员相信这篇深度解析都能让你对“贪心”有更立体的认识。2. 问题背景与核心需求解析2.1 原题场景还原与抽象建模我们先来还原一下题目的大致场景基于常见的竞赛题风格进行合理重构假设我们有n本书每本书都有一定的页数。现在需要将这些书分配给m个抄写员进行抄写。每个抄写员必须抄写连续序列的书比如不能把第一本和第三本给同一个人而跳过第二本。每个抄写员的抄写速度是相同的因此他们所花费的时间正比于分配到的书的总页数。我们的目标是找到一种分配方式使得所有抄写员中抄写页数最多的那个人其工作量总页数尽可能小。换句话说我们要最小化最大子段和。这是一个非常经典的“最小化最大和”问题在资源分配、负载均衡等领域有广泛的应用。例如将一批任务分配给多个处理器使得最忙的处理器的完成时间最短或者将数据块分配到多个磁盘使得负载最重的磁盘数据量最小。2.2 问题形式化定义与输入输出为了后续讨论清晰我们将问题形式化输入两个整数n和m表示书的总数和抄写员的数量。(1 m n 10^5)典型数据范围。n个正整数a[1], a[2], ..., a[n]表示每本书的页数。输出一个整数ans表示在最优分配方案下抄写页数最多的那个抄写员需要抄写的最小页数。有时题目还会要求输出具体的分配方案即每个抄写员负责哪几本书。本篇重点讨论核心的最优值求解方案输出可作为延伸练习。核心矛盾m个抄写员是有限的资源。如果m很大接近n我们可以让每个人只抄一本书那么最大工作量就是最厚的那本书的页数。如果m很小比如为1那么所有书都由一个人抄最大工作量就是所有书的总页数。一般情况下我们需要在“分段”和“合并”之间找到平衡让每段的和尽可能均匀。3. 算法思路演进从暴力到贪心再到二分答案3.1 暴力搜索与动态规划的不可行性最直观的想法是枚举所有可能的分割点。在n本书的n-1个空隙中选择m-1个位置进行分割将书分成m个连续段。计算每种分法下最大段的和然后取最小值。这是一个组合数问题计算量是C(n-1, m-1)在n和m较大时完全不可行。另一个思路是动态规划DP。定义dp[i][k]为将前i本书分配给k个抄写员的最小化最大工作量。状态转移需要考虑最后一个抄写员负责从j1到i的书即dp[i][k] min{ max(dp[j][k-1], sum(j1, i)) }其中sum(j1, i)表示第j1到第i本书的页数和。这个DP的时间复杂度是O(n^2 * m)在n达到10^5量级时也无法承受。注意这里涉及区间和的计算通常需要用前缀和数组prefix来优化使得sum(j1, i) prefix[i] - prefix[j]可以在O(1)时间内得到。但即便如此O(n^2 * m)的复杂度依然太高。3.2 贪心策略的初步尝试与陷阱既然标签是贪心我们首先尝试设计贪心策略。一个常见的错误贪心是每次尽可能让当前抄写员多抄直到再抄下一本就会使他成为“当前最大”时就换下一个抄写员。具体来说设定一个“当前最大工作量”的预期值limit初始可以设为单本书的最大页数或者平均页数然后遍历书本累加页数。如果当前累加和加上下一本书的页数会超过limit就让当前抄写员停止从下一本书开始新的累加即分配给下一个抄写员。最后看需要多少抄写员。这个策略的问题在于limit的值是未知的且这个策略对limit非常敏感。如果我们limit设得太大可能只需要少于m个抄写员如果设得太小可能需要多于m个抄写员。我们的目标恰恰是找到那个最小的limit使得恰好或至少能用m个抄写员分配完所有书。因此单纯的“过程贪心”无法直接得出答案它需要一个“目标值”来驱动。这引出了本题乃至这一类问题的核心解法框架二分答案 贪心验证。3.3 二分答案框架的引入我们发现如果给定一个猜测的答案X即假设最大工作量不超过X我们可以很容易地判断是否可行。判断方法就是上面提到的贪心策略初始化当前抄写员计数cnt 1当前抄写员累计页数current_sum 0。遍历每一本书i页数为a[i]如果current_sum a[i] X说明当前抄写员不能再抄这本书了否则会超负荷。那么我们就启用一个新的抄写员cnt 1让新抄写员从这本书开始抄current_sum a[i]。这里有个关键细节必须判断单本书的页数a[i]是否本身就大于X。如果是那么任何包含这本书的分配方案都会导致工作量超过X因此这个X直接不可行。我们在编码时需要加上这个检查。否则current_sum a[i] X就让当前抄写员继续抄这本书current_sum a[i]。遍历结束后如果使用的抄写员数量cnt m说明在最大工作量不超过X的限制下可以用不超过m个人完成所有工作因此X是一个可行的上界。如果cnt m说明X太小了限制太严格需要更多的人才能完成因此X不可行。这个验证函数check(X)的时间复杂度是O(n)非常高效。现在问题转化为寻找最小的可行X。显然X的取值范围是下界L至少是单本书的最大页数。因为总有一本书需要被一个人抄。上界R最坏情况下所有书由一个人抄即所有书的总页数。在这个有序范围[L, R]内满足check(X)为真的X构成一个连续的区间例如如果X可行那么任何大于X的值也一定可行。我们的目标是找到这个区间的左端点即最小值。这完美符合二分查找Binary Search的应用场景——在有序序列中寻找第一个满足条件的值。二分查找的过程初始化left L,right R。while (left right):计算中间值mid left (right - left) / 2。注意防止溢出调用check(mid)。如果check(mid)为真说明mid是一个可行解并且答案可能更小或等于mid。因此将搜索范围缩小到左半部分right mid。如果check(mid)为假说明mid太小了不可行。答案一定在更大的那边。因此将搜索范围缩小到右半部分left mid 1。循环结束时left或right的值就是最小的可行X即所求答案。这个“二分答案贪心验证”的框架将原本复杂的优化问题分解为一个简单的判定问题和一个高效的搜索过程是算法竞赛中处理“最小化最大值”或“最大化最小值”问题的标准套路。4. 核心细节解析与实操要点4.1 贪心验证函数check(X)的编码细节与边界处理check函数的实现虽然思路简单但边界情况处理不好极易出错。下面给出一个稳健的实现模板以C为例bool check(long long limit, vectorint pages, int m) { int cnt 1; // 至少需要一个抄写员 long long current_sum 0; for (int page : pages) { // 关键检查如果单本书页数就超过限制直接不可行 if (page limit) { return false; } if (current_sum page limit) { // 当前抄写员装不下了需要新开一个 cnt; if (cnt m) { // 如果抄写员数量已经超了提前返回失败 return false; } current_sum page; // 新抄写员从当前这本书开始 } else { current_sum page; // 当前抄写员继续抄 } } return cnt m; // 最终使用的抄写员数不超过m则可行 }实操要点与避坑指南数据类型页数之和可能很大n最大为10^5每本书页数假设最大为10^4总页数可达10^9超出了32位整型int的范围。因此current_sum、limit、以及二分查找中的left,right,mid都必须使用long long64位整型。提前退出优化在循环内部一旦发现cnt m就可以立刻返回false无需遍历完所有书。这是一个重要的常数优化。单本书超限检查if (page limit)这个检查至关重要。没有它如果limit小于某本书的页数current_sum page limit的判断逻辑虽然最终也会导致cnt激增而返回false但逻辑上不清晰且在某些变体问题中可能出错。cnt的初始值必须为1。因为至少需要一个人开始抄第一本书。如果初始化为0逻辑上会多出一轮判断容易混乱。4.2 二分查找的“左闭右开”与“左闭右闭”区间选择二分查找是易错点。上面给出的是“左闭右闭”区间[left, right]的写法并且寻找的是第一个满足条件的值即“最小可行值”。这种写法的循环条件是while (left right)更新策略是right mid和left mid 1。最终left和right相等即为答案。另一种常见写法是“左闭右开”区间[left, right)。在这种写法下right初始化为R 1一个不可行的位置循环条件仍是while (left right)更新策略为如果check(mid)为真则right mid如果为假则left mid 1。循环结束后left是答案。个人经验我强烈推荐并始终使用“左闭右闭”的写法并明确记住“找第一个可行解”的模板。这更容易理解且不易出错。关键点在于mid的计算mid left (right - left) / 2这是标准的防溢出写法。当check(mid)为真时说明mid可能就是答案或者答案在左边所以right mid保留mid。当check(mid)为假时说明mid肯定不是答案答案在右边所以left mid 1排除mid。4.3 复杂度分析与适用场景总结时间复杂度二分查找的复杂度为O(log(R-L))其中R-L最大为总页数约为10^9量级log2(10^9)约为30。每次验证check需要O(n)。因此总复杂度为O(n log(SUM))对于n10^5是绰绰有余的。空间复杂度主要是存储书页数组O(n)和几个变量O(1)。这种方法之所以强大是因为它将“求最优解”这个本身可能很难的问题转化为了“判断一个解是否可行”这个相对简单的问题。只要验证函数check是单调的即如果X可行则所有大于X的值也可行并且可以在多项式时间内完成二分答案就是一把利器。适用场景特征问题的答案在一个确定的范围内。对于给定的一个候选答案容易判断其是否可行或是否满足某个条件。可行性函数具有单调性。5. 完整代码实现与逐行解析下面给出基于上述思路的完整C代码实现并附上详细注释。#include iostream #include vector #include algorithm using namespace std; typedef long long ll; // 使用long long防止溢出 // 贪心验证函数判断在最大工作量不超过limit的情况下能否用不超过m个抄写员完成 bool check(ll limit, const vectorint pages, int m) { int cnt 1; // 需要的抄写员数量初始为1 ll current_sum 0; // 当前抄写员累计页数 for (int page : pages) { // 如果单本书页数超过限制绝对不可能分配 if (page limit) { return false; } // 如果当前抄写员加上这本书会超负荷则启用新抄写员 if (current_sum page limit) { cnt; // 增加抄写员计数 // 如果抄写员数已经超过m提前结束返回不可行 if (cnt m) { return false; } current_sum page; // 新抄写员从这本书开始抄 } else { // 否则当前抄写员可以继续抄这本书 current_sum page; } } // 遍历完所有书若所需抄写员数不超过m则此limit可行 return cnt m; } int main() { int n, m; cin n m; vectorint pages(n); ll left 0; // 二分下界初始为0但会被更新为最大单本书页数 ll right 0; // 二分上界初始为0累加为总页数 for (int i 0; i n; i) { cin pages[i]; right pages[i]; // 上界所有书页数之和 if (pages[i] left) { left pages[i]; // 下界单本书的最大页数 } } // 二分查找最小的可行limit ll ans right; // 初始化答案为上界最坏情况 while (left right) { ll mid left (right - left) / 2; // 防止溢出的取中方法 if (check(mid, pages, m)) { // 如果mid可行尝试寻找更小的可行解 ans mid; // 更新答案为当前可行的mid right mid - 1; // 收缩右边界 } else { // 如果mid不可行说明解在更大的那边 left mid 1; // 收缩左边界 } } // 输出答案 cout ans endl; return 0; }代码解析与关键点输入与初始化在读取数据的同时就计算好了二分的初始边界left最大单本书页数和right总页数。这是一个小优化避免再次遍历数组。二分循环条件这里使用了while (left right)这是另一种“左闭右闭”的写法。当left right时循环结束。这种写法下ans需要在check为真时及时更新。最终ans存储的就是我们找到的最小可行值。ans的初始化初始化为right总页数这是绝对可行的最大值。在二分过程中我们只会用更小的可行值去更新它。防溢出mid left (right - left) / 2是计算中间值的标准安全写法避免了(left right) / 2可能导致的溢出。6. 变体拓展与相关问题联想掌握了“书页”/“抄写员”问题的解法你就掌握了一类问题的通解。下面列举几个本质相同或高度相关的问题可以帮助你举一反三“分割数组的最大值”LeetCode 410这是本题的英文原题描述几乎一致。“在 D 天内送达包裹的能力”LeetCode 1011传送带上的包裹必须在D天内运完求传送带的最小运载能力。将“包裹重量”类比“书页数”“天数”类比“抄写员数”完全一样。“制作 m 束花所需的最少天数”LeetCode 1482花园里有n朵花每朵花在第bloomDay[i]天开放。需要制作m束花每束需要k朵相邻的、已经开放的花。求最少需要等待多少天。这里“天数”是二分的答案验证函数check(day)是判断在第day天能否找到足够的连续k朵已开放的花来组成m束。“小张刷题计划”类似题目可能增加“跳过某些难题”的变体但核心二分框架不变。解题思维定式当你看到问题描述中出现“最小化最大值”、“最大化最小值”、“在...条件下求至少/至多...”这类字眼并且数据范围暗示O(n^2)DP会超时就应该立刻想到“二分答案”这个方向。然后集中精力设计那个O(n)或O(n log n)的贪心验证函数check。7. 常见错误与调试技巧实录在实际编码和调试中我遇到过不少坑这里分享给大家整数溢出这是最隐蔽的错误。没有使用long long在计算总和或mid时n和页数稍大就会溢出导致二分循环无法结束或结果错误。务必在读取数据后估算最大可能值。二分查找死循环主要发生在更新left和right时。牢记你选择的区间形式和寻找的目标第一个可行还是最后一个可行。如果循环一直无法退出通常是更新语句写错了。可以用小的样例数据打印出每一步的left,right,mid和check(mid)结果来调试。贪心验证逻辑错误忘记检查单元素超限如之前所述这是必须的。cnt初始值错误如果初始化为0需要在循环开始前处理第一本书逻辑变得复杂容易出错。初始化为1更自然。条件判断顺序先判断current_sum page limit还是先判断cnt m通常先判断是否超限再增加cnt并判断是否超过m逻辑更清晰。像上面代码那样在增加cnt后立刻判断cnt m并返回是高效的写法。样例能过提交WA边界条件测试m n的情况每人一本答案应该是最大页数。测试m 1的情况一人全抄答案应该是总页数。极端数据所有书页数相同书页数递增或递减n和m都等于1。对拍写一个暴力搜索或DP程序用于小数据n 20用随机生成的数据与你的二分答案程序对比结果。这是发现逻辑错误最有效的方法。调试表格当你对验证函数不确定时可以手动模拟一个小例子。书页数组[10, 20, 30, 40, 50]猜测 limit贪心分配过程70[102030]60, [40], [50]65[102030]60, [40], [50]64[102030]60, [40], [50]63[102030]60, [4050]90 (超限) - [1020]30, [3040]70 (超限) - [10]10, [2030]50, [40], [50]从这个表可以直观看出limit从70降到65、64时分配方案不变cnt都是3。当limit降到63时第一个抄写员无法装下40导致分段变多需要4个人因此不可行。所以最终答案应该是64。8. 从“书页”题升华的贪心算法心得回过头看这道“书页”题它的标签虽然是“贪心”但纯粹的贪心策略不结合二分很难直接求解。这给我们一个重要的启示贪心算法往往不是孤立的它常常作为一种高效的“子过程”或“验证工具”嵌入到更大的算法框架中如二分答案、动态规划。贪心算法的核心在于“局部最优选择能导致全局最优解”。但如何定义“局部最优”这需要我们对问题有深刻的理解和证明。在“书页”题的验证函数check中我们的贪心策略是“在不超过上限limit的前提下尽可能让当前抄写员多抄”。这个策略对于“判断给定limit是否可行”这个问题是正确且最优的因为如果存在一种可行分配我们总可以通过调整让前面的人尽可能多抄而不影响可行性。这种“尽可能填满”的思想是很多贪心验证的基础。最后再强调一下这类问题的解题流程识别题型最小化最大值/最大化最小值。确定二分框架分析答案上下界设计check函数。实现验证函数用贪心或其它线性/近线性方法实现check。完成二分查找注意边界和更新条件。测试与调试用边界数据和随机小数据对拍。这道题就像一把钥匙帮你打开了“二分答案”这扇大门。以后遇到类似的题目你就能迅速抓住本质化繁为简。算法学习就是这样吃透一道经典题胜过盲目刷十道陌生题。