1. 这道复制书稿到底在考什么1.1 先把题目场景翻译成人话很多同学第一次看到复制书稿这个标题脑子里想的是打字员坐在办公室里抄稿子的画面实际上这道题的本质是一道披着故事外衣的区间划分 最优化问题。把题目翻译成人话就是给你一串页数比如 1、2、3、4、5、6、7、8、9再给你 k 个人让你把这串数字切成 k 段连续的区间每一段的代价是该段内所有页数之和要求让所有段里最大代价尽可能小。这就是信息学奥赛一本通 1278 【例9.22】复制书稿也就是洛谷 P1281 书的复制这道经典题的核心。刚接触这道题的朋友经常会把复制时间最短理解成总共花的时间最短然后一头扎进排序或者贪心地想让每个人抄得一样多。这个理解是偏的。题目里每个人的速度一样而且大家是同时开工的所以总耗时并不等于所有人时间相加而是等于那个抄得最多的人所用的时间。换句话说你真正要压的是最慢的那个人的工作量这就是一个典型的最大值最小化问题是二分答案这套方法论最经典的练手题之一。为什么这道题值得单拎出来讲因为它同时把三件事拧在一起判单调性、写 check 函数、以及在多解情况下按题目要求构造出特定的那一组解。前两件事是所有二分答案题的通用套路后一件事才是这道题的魂——它逼着你思考当最优值有多个可行方案时凭什么选我这一组。很多同学二分对了答案却在最后一步划分区间时输出得跟样例不一样就是卡在这里。适合谁来读这篇内容如果你已经学过基础的循环、数组、函数但一遇到最大值最小就不知道从哪下手那这篇正好对味如果你已经会套二分模板但每次都栽在最后输出那更要往下看我会把从后往前贪心这个反直觉的操作掰开揉碎讲清楚。哪怕你是纯小白只要能读懂数组和循环跟着走一遍也能把这道题啃下来。1.2 两个平台的版本差异别踩这个隐形的坑信息学奥赛一本通 1278 和洛谷 P1281 讲的是同一道题题面几乎一字不差但真正提交的时候你会发现两边对输出的细节要求表述略有不同。一本通上的描述是k 行的起始编号应该从小到大排列如果有多解则尽可能让前面的人少抄写洛谷 P1281 的表述是共 k 行第 i 行表示第 i 个人抄写的书的起始编号和终止编号k 行的起始编号应该从小到大排列如果有多解那么使前面的人尽量少抄。表面上说的是同一件事但前面的人尽量少抄这句话直接决定了你贪心的方向。这里有一个特别容易被忽略的点当人比书多的时候也就是 k 大于书的数量 m 时必然有若干个人是没书可抄的。这些空出来的人该放在输出列表的哪个位置答案是放在最前面输出0 0。因为题目要求让前面的人尽量少抄那前面的人干脆一本都不抄把书全交给后面的人这正好契合题意。我见过太多人这道题二分写对、划分也对唯独在处理m k的时候把空段放到了末尾导致结果与标准答案对不上。注意一本通和洛谷虽然本质同题但在你抄题解对照时务必以你实际提交平台上的题面描述为准。尤其是输出格式里关于多解取哪一组的措辞差一个字都可能让你换一种贪心方向。还有一点小细节值得提一嘴题目说的是一本书不允许分给两个或以上的人抄写分给同一个人的书必须连续。这句话里连续两个字非常关键它直接锁死了问题的形态——你不是在自由地往背包里塞东西你是在一串有序序列上切 k-1 刀。如果书可以乱序分配那这题就变成了另一类问题比如用堆做负载均衡难度和解法完全不同。所以读题时抓住连续这个词你就抓住了整道题的骨架。1.3 一道题串起三个知识点如果把这道题的收获拆开来看它至少能给你三个可迁移的能力。第一是识别最大值最小化 / 最小值最大化的信号只要看到让最大的那个尽可能小脑子里就该条件反射地想到二分答案。第二是设计 check 函数也就是给定一个上限 T判断能不能用不超过 k 个人完成任务这是二分答案的核心引擎。第三是在可行域里挑出符合附加条件的那组解这一步往往比二分本身更能体现选手的细心程度。这三个能力不止在这道题里用得上。往远了说洛谷 P1182 数列分段、洛谷 P2678 跳石头、P3853 路标设置本质上都是最大值最小化 贪心 check的变体。你把复制书稿这道题吃透等于拿到了一把能开好几把锁的钥匙。所以别把它当成一道孤立的例题把它当成一个模板去理解后面遇到同族题你会轻松很多。2. 核心思路拆解为什么是二分加贪心2.1 从左到右枚举 vs 二分答案最朴素的想法是什么样的枚举一个答案 T从最小的可能值开始一个一个往上试第一个能让 k 个人抄完的 T 就是答案。这个思路没错但慢得离谱。假设总页数是一千万你从 1 枚举到一千万每次还要 O(m) 去检查复杂度直接爆炸。而且这道题每本书的页数可能很大枚举的区间非常宽这在竞赛里必然超时。换成二分就舒服多了。二分答案的前提是答案具有单调性如果某个上限 T 能用 k 个人把书抄完那么任何比 T 更大的上限 T 也一定能抄完反过来如果 T 抄不完那比 T 更小的值更抄不完。这个单调性在这道题里是天然成立的——你把每个人的容量放宽只会让分配更容易绝不会更难。有了单调性我们就能在[最大单本页数, 总页数]这个区间里二分每次砍掉一半几十次就能锁定答案。打个生活化的比方你要找一个能装下所有行李的最小箱子从大到小一个个试太蠢但如果告诉你箱子越大越可能装得下那你就可以先试中号的装不下就换大号装得下就换小号很快逼近临界值。二分答案就是这种试探的算法化表达。2.2 二分的对象为什么是最长抄写时间这里有个新手常见困惑我到底该二分什么是二分人数吗还是二分页数答案是二分**最长那个人抄写的页数上限**也就是问题要求你最小化的那个量。因为最终目标是让最慢的人尽量快所以这个单人最多抄多少页正是我们想要压到最小的目标。确定了二分对象二分的范围也就清楚了。下界最小可能值应该是所有书里页数最大的那本因为无论怎么分抄到那本书的人至少得抄这么多不可能更少。上界最大可能值自然是所有书的总页数也就是最极端的一个人全抄完。把这两个边界记牢能让你的二分少走很多弯路尤其是下界如果设成 1遇到页数很大的数据时会白白多跑很多轮。提示下界设成max(a[i])而不是 1是这道题的一个小优化也是判断某本单书本身超过上限这类边界的一种自然处理方式。设好了check 函数里甚至可以省掉单本超限的判断。2.3 贪心方向的选择为什么要从后往前这是全文最需要讲透的一点。复制书稿这道题最难的地方不在二分而在最后怎么把最优值转成一个具体的划分方案并且这个方案要满足多解时让前面的人少抄。很多人到这里就懵了我怎么知道哪个方案才是题目要的那个关键就在从后往前这四个字。我们来推一下逻辑。题目说多解时前面的人尽量少抄等价于后面的人尽量多抄。那我要构造方案时就应该从最后一本书开始往前扫每当能往当前这个人身上多塞一本且不超过上限 T就塞进去。这样后面的人会尽可能地被喂饱前面的人自然就分配得少。反之如果你从前往后贪心前面的人会先把书搬走前面的人反而抄得多跟题目要求正好相反。用一个更直观的类比分蛋糕时要求前面的孩子少分点那你当然要从队伍最后面开始切最后面的孩子先把大块拿走剩下的留给前面前面自然就少了。从后往前扫本质就是让贪心的主动权落在后面的人手里。不过要注意从后往前贪心构造出来的方案段与段之间的顺序是倒着记录的。也就是说你第一个扫出来的区间是最后一本所在的那一段输出的时候必须把顺序翻转过来按照第一段在前、最后一段在后的顺序打印。这一点如果你没意识到输出的行序就是反的跟样例一对比立马露馅。2.4 为什么不做动态规划有同学会想这题不是典型的划分型 DP吗用f[i][j]表示前 i 本书分给 j 个人抄的最小最大时间然后转移一下不也能做确实能做思路也正确但在这道题的规模下DP 是杀鸡用牛刀而且很容易写错转移方程、写错没必要的初始化。更重要的是DP 在多解取哪一组这一步上处理起来远不如贪心直观。二分加贪心的组合时间复杂度是 O(m log(sum))快、短、稳。而划分型 DP 大概是 O(m² k) 甚至 O(m k) 级别码量翻倍还要处理前缀和。对这道题而言没有任何理由舍近求远。这也是我特别想强调的一点看到最大值最小化 连续划分先想二分答案而不是 DP。除非题目还附加了别的奇怪约束比如每段长度有额外限制、要计数方案数才考虑别的法子。3. 手把手拆解实现步骤3.1 数据读入与二分边界确定先把东西读进来。题目给的是 m 和 k紧接着是 m 个整数表示每本书的页数。我习惯用一个long long数组存页数边读边统计总和同时顺便记录最大值。为什么不直接用int因为有些版本的数据总和会逼近int的上限为了不给自己埋雷长期养成长整型防御的习惯是值得的。读完之后二分的下界就是那本最厚的书的页数上界就是总页数。这里要特别留意一种极端情况如果书的数量比人还少也就是说有些人是空手的那答案的上界其实就是最厚那本书的页数因为再厚的书也得有人抄而且只需一个人。这种情况虽然二分依然能正确跑出结果但输出时就要额外处理空段我在 3.5 节会专门讲。注意读入时别忘记同步维护sum和maxv否则你后面还得再扫一遍数组多一次遍历虽然不致命但体现不出老手的效率意识。3.2 check 函数怎么写才不翻车check 函数是这道题的引擎它回答一个问题给一个上限limit最少需要几个人才能抄完。写法上我从最后一本书往前扫维护一个当前这个人已经抄了多少页的累加器sum。每遇到一本书如果塞进去不超过limit就塞如果塞进去会超就说明当前这个人装满了换下一个人并把这本新书作为新人的第一本。扫完后统计出来的段数就是最少需要的人数。这里有个非常关键的判断统计出来的人数如果小于等于k说明在这个上限下是可行的因为人手有富余大不了让某些人少抄点。如果大于k就说明人不够上限太紧了得放宽。注意是小于等于不是等于很多同学在这里写成cnt k就返回真结果当人手富余时反而判成不可行二分答案直接跑偏。bool check(long long limit) { int cnt 1; // 至少需要一个人 long long sum 0; for (int i m; i 1; --i) { if (a[i] limit) return false; // 单本超限直接不可能 if (sum a[i] limit) { cnt; // 换一个人 sum a[i]; } else { sum a[i]; } } return cnt k; }为什么从后往前扫 check 也一样成立因为判断可行性只看段数方向不影响段数的最小值。从后往前扫只是为了和后面构造方案时的方向保持一致逻辑上更顺避免来回切换思维。你从前往后扫 check 同样能得到正确答案但只要最后划分方案是从后往前的统一起来更不容易出错。3.3 二分主循环与答案记录二分的模板有两种写法我用的是记录答案 收缩区间那种最不容易写错。循环条件是lo hi每次取mid如果 check 通过说明这个上限可行那就记下答案并往更小的方向收缩hi mid - 1如果不通过就往大的方向扩lo mid 1。循环结束时ans里存的就是最小的可行上限。long long lo maxv, hi sum, ans sum; while (lo hi) { long long mid lo (hi - lo) / 2; if (check(mid)) { ans mid; hi mid - 1; } else { lo mid 1; } }这里的mid lo (hi - lo) / 2是为了防止lo hi溢出。虽然这道题的数据未必大到溢出但这就是个肌肉记忆写习惯了就不会在别的题上翻车。3.4 从后往前构造最优解拿到最小的可行ans之后要重新从最后一本书往前扫一遍这次是真的在划分区间。思路是维护当前段的和sum以及当前段的右端点curEnd。从 m 号书开始往前能塞就塞进当前段塞不进去就封口——把当前段的[i1, curEnd]记下来然后开一个新段curEnd更新为当前的 isum重置为这本新书的页数。扫完之后别忘了把最后一段也就是最前面那段也记上。因为循环结束时第一本书所在的段还没有被封口容易漏掉。很多人写完循环直接输出了结果第一段凭空消失答案少一行。vectorpairint,int seg; long long sum2 0; int curEnd m; for (int i m; i 1; --i) { if (sum2 a[i] ans) { seg.push_back({i 1, curEnd}); // 封口一段 curEnd i; sum2 a[i]; } else { sum2 a[i]; } } seg.push_back({1, curEnd}); // 补上最前面那段注意seg里现在是从后往前的顺序seg[0]是最后一段seg.back()是第一段。输出时要倒过来遍历。3.5 处理人比书多的边界情况如果 k 大于实际需要的段数说明有多余的人手。按照题目让前面的人少抄的要求这些空手的人应该排在最前面输出0 0。所以输出顺序是先打印k - seg.size()行0 0然后从seg的末尾往前打印每一段的起止编号。int extra k - (int)seg.size(); for (int i 0; i extra; i) cout 0 0\n; for (int i (int)seg.size() - 1; i 0; --i) cout seg[i].first seg[i].second \n;为什么要确保extra非负因为二分保证了seg.size() k否则说明你的ans选大了或者贪心逻辑有问题。如果你发现extra是负数那一定是前面哪一步出了岔子回头查 check 函数和贪心封口的条件。4. 完整代码与样例走查4.1 可提交的 C 完整实现把上面的碎片拼起来就是一份可以直接提交的代码。这份代码在两个平台上都能通过除非平台对输出格式另有极端限制。我特意把变量命名得清晰一点方便你对照理解。#include bits/stdc.h using namespace std; int m, k; long long a[505]; bool check(long long limit) { int cnt 1; long long sum 0; for (int i m; i 1; --i) { if (a[i] limit) return false; if (sum a[i] limit) { cnt; sum a[i]; } else { sum a[i]; } } return cnt k; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin m k; long long maxv 0, total 0; for (int i 1; i m; i) { cin a[i]; maxv max(maxv, a[i]); total a[i]; } long long lo maxv, hi total, ans total; while (lo hi) { long long mid lo (hi - lo) / 2; if (check(mid)) { ans mid; hi mid - 1; } else { lo mid 1; } } vectorpairint,int seg; long long sum 0; int curEnd m; for (int i m; i 1; --i) { if (sum a[i] ans) { seg.push_back({i 1, curEnd}); curEnd i; sum a[i]; } else { sum a[i]; } } seg.push_back({1, curEnd}); int extra k - (int)seg.size(); for (int i 0; i extra; i) cout 0 0\n; for (int i (int)seg.size() - 1; i 0; --i) cout seg[i].first seg[i].second \n; return 0; }ios::sync_with_stdio(false)加cin.tie(nullptr)是竞赛里输入输出提速的常规操作虽然这道题数据量不大但养成习惯不亏。数组开成 505 是因为洛谷 P1281 的 m 最大到 500留一点余量更稳妥。4.2 关键变量含义对照写代码最怕的是变量一多就晕尤其是这道题里sum出现了两次check 里一次构造方案里一次curEnd又是个容易搞混的边界。我整理了一张对照表帮你把每个变量的职责钉死。变量名所在位置含义易错点limitcheck 参数二分试探的单人上限别和最终答案ans混用cntcheck 内在上限下最少需要的人数初值要设 1不是 0sumcheck / 构造当前段已累计的页数两处逻辑一致但要独立ansmain二分收敛后的最小可行上限二分结束时才可用curEnd构造当前正在处理的段的右端点初始为 mseg构造记录所有划分段顺序是反的输出要翻转extra输出空手的人数应为非负把这张表记住你写代码时心里就有谱了不会出现这个 sum 到底是哪个 sum的困惑。4.3 样例执行过程逐步演示拿样例9 3和页数1 2 3 4 5 6 7 8 9来走一遍你会对整道题的运行机理有更深的体会。总页数是 45最厚的书是 9 页所以二分区间是[9, 45]。程序会不断试探最终收敛到ans 17。为什么是 17因为用 17 能刚好分成三段[1,5]共 15 页、[6,7]共 13 页、[8,9]共 17 页最大值是 17。如果上限压到 16从后往前试最后一段最多能装下9817超了只能装[9,9]或者[8,9]也超……你会发现至少需要 4 段才能塞下人手不够所以 16 不可行。17 就是临界点。接着构造方案从 i9 往前扫sum一开始装 9加 8 变成 17 还没超加 7 会变成 24 超了于是封口[8,9]新段从 7 开始装 7加 6 得 13加 5 超了封口[6,7]新段从 5 开始装到 1得 15不超最后补上[1,5]。seg里存的是[8,9]、[6,7]、[1,5]倒序输出就是1 5、6 7、8 9跟样例完全一致。你看整个流程走下来每一步都是可解释、可复现的这就是理解了原理和死记模板的区别。5. 调试实录我踩过的那些坑5.1 二分边界写错导致的连环翻车第一个坑是二分循环条件写错。有的同学写while (lo hi)然后里面mid的更新又是对方向的很容易在某个边界上卡死程序陷入死循环。我建议一律用while (lo hi)配上记录答案 收缩的写法逻辑最直白可行就记下来往小收不可行就往大扩循环自然结束。这种写法不容易死循环也不容易漏解。第二个相关的坑是下界设成 0 或 1。如果某本书的页数本身就是答案比如 k1 时答案就是总页数或者书少人多时答案就是最厚那本下界设太低会让二分多跑不少没必要的轮次。虽然不影响正确性但既然我们知道答案不可能小于最厚那本书为什么不把边界收紧呢把下界设成maxv是一个又省事又稳妥的选择。5.2 输出顺序反了的经典症状这是这道题最高频的错误没有之一。症状是你把样例跑一遍发现每段的内容都对但行的顺序整个倒过来了1 5跑到了最后一行8 9跑到了第一行。原因就是你从后往前扫seg里的顺序是反的输出时忘了翻转。这个错误非常隐蔽因为如果你只检查每段的页数和是不是没超上限你会觉得自己完全正确。解决它很简单输出时用倒序遍历seg。同时提醒自己extra那些0 0是排在最前面的别把它们也放到循环里去翻转。5.3 空段位置放错的迷惑操作当 k 大于书的数量时会出现空手的人。我见过有人把这些0 0放在输出的最后理由是反正这些人没干活放后面也合理。但题目明确要求让前面的人少抄空手的人应该被视为抄得最少的人所以放前面才对。如果你放了后面虽然每段的页数上限看起来依然满足但和标准答案一比对就露馅了。注意判断到底有多少个空段靠的是k - seg.size()而不是k - m。因为即使书的数量大于等于人也可能因为页数分布的关系导致实际只用了不到 k 段比如某些书很小几个人就能合并抄完。所以空段数量必须用实际段数来算。5.4 常见问题速查表为了让你在调试时能快速定位我把这道题常见的错误症状和原因整理成了表格。遇到问题先对照这张表能省下大量对拍时间。症状可能原因排查方向结果比标准答案大check 函数判成小于 k 才算可行检查cnt k输出行序颠倒忘了翻转 seg 输出顺序倒序遍历 seg第一段丢失循环结束后忘了补最后一段检查seg.push_back({1, curEnd})空段位置不对把0 0放在了末尾空段应放在最前面程序死循环二分条件与更新不匹配改用lo hi模板段内页数超限构造时sum a[i] ans写成检查放宽条件单本超过上限被忽略check 没判断单本加a[i] limit拦截大数据超时用了线性枚举而非二分确认二分收敛这张表我调这道题的时候是逐行验证过的尤其是段内页数超限那一行和一字之差会让你的划分在临界点崩溃段和刚好等于ans的边界情况被错误拆开进而多出一段。写条件判断时一定要想清楚等于上限是允许的只有严格超过才需要换人。5.5 一个容易被忽视的细节第一个人抄多少题目要求让前面的人少抄指的是在保证最优值不变的前提下把尽可能多的书往后推。我构造方案时从后往前贪心正是为了实现这个目标。但你要验证一下从后往前贪心得到的方案是不是真的满足前面的人少。答案是肯定的因为后面的人在每一步都尽可能多装不超上限最后留给前面的必然是能少则少。这个贪心的正确性可以这样理解既然总段数固定后面的人多抄一本前面的人就必然少抄一本而我们的策略让后面的人能多抄就多抄所以前面的人被压到了最小。有同学会问那如果从后往前装满了但前面最后一段的页数仍然比某个人多会不会违反前面的人少抄不会因为前面的人少抄是相对于同样最优值下的其他方案而言的不是要求绝对页数递增。只要在所有可行方案里你是让前面的人抄得最少的那一类就满足了题意。6. 举一反三这类题的通用套路6.1 二分答案类题的三大判别特征以后你再拿到一道题怎么判断它是不是二分答案题我总结了三个特征只要中了两个基本就可以往二分方向想。第一题目问的是最大值最小或最小值最大比如让最慢的人最快让最短的一段尽量长。第二答案具有明显的单调性某个值可行比它宽松的值一定也可行。第三题目规模通常不小正向枚举或 DP 会超时逼着你用对数级别的方法去逼近答案。复制书稿这三个特征全中所以它是二分答案的教科书级范例。洛谷 P1182 数列分段也是同款——把一段数列分成不超过 M 段让每段和的最大值最小几乎和这题一模一样只是少了输出方案的麻烦。这类题的通用框架就是确定二分对象、确定可行边界、写 check 贪心、二分收敛、按需构造方案。把这五步刻在脑子里遇到同族题就能快速上手。6.2 从这道题能带走的通用思维抛开代码本身这道题真正训练的是两种思维。第一种是把最优化问题转成可行性判定与其直接求最小是多少不如问某