企业官网建设流程全解析

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 号书开始往前，能塞就塞进当前段，塞不进去就"封口"——把当前段的[i+1, curEnd]记下来，然后开一个新段，curEnd更新为当前的 i，sum重置为这本新书的页数。

扫完之后，别忘了把最后一段（也就是最前面那段）也记上。因为循环结束时，第一本书所在的段还没有被封口，容易漏掉。很多人写完循环直接输出了，结果第一段凭空消失，答案少一行。

vector<pair<int,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; } } vector<pair<int,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又是个容易搞混的边界。我整理了一张对照表，帮你把每个变量的职责钉死。

把这张表记住，你写代码时心里就有谱了，不会出现"这个 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，从后往前试：最后一段最多能装下9+8=17超了，只能装[9,9]或者[8,9]也超……你会发现至少需要 4 段才能塞下，人手不够，所以 16 不可行。17 就是临界点。

接着构造方案，从 i=9 往前扫，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。如果某本书的页数本身就是答案（比如 k=1 时答案就是总页数，或者书少人多时答案就是最厚那本），下界设太低会让二分多跑不少没必要的轮次。虽然不影响正确性，但既然我们知道答案不可能小于最厚那本书，为什么不把边界收紧呢？把下界设成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 常见问题速查表

为了让你在调试时能快速定位，我把这道题常见的错误症状和原因整理成了表格。遇到问题先对照这张表，能省下大量对拍时间。

这张表我调这道题的时候是逐行验证过的，尤其是"段内页数超限"那一行，>和>=一字之差，会让你的划分在临界点崩溃，段和刚好等于ans的边界情况被错误拆开，进而多出一段。写条件判断时一定要想清楚：等于上限是允许的，只有严格超过才需要换人。

5.5 一个容易被忽视的细节：第一个人抄多少

题目要求"让前面的人少抄"，指的是在保证最优值不变的前提下，把尽可能多的书往后推。我构造方案时从后往前贪心，正是为了实现这个目标。但你要验证一下：从后往前贪心得到的方案，是不是真的满足"前面的人少"。答案是肯定的，因为后面的人在每一步都尽可能多装（不超上限），最后留给前面的必然是能少则少。这个贪心的正确性可以这样理解：既然总段数固定，后面的人多抄一本，前面的人就必然少抄一本，而我们的策略让后面的人"能多抄就多抄"，所以前面的人被压到了最小。

有同学会问，那如果从后往前装满了，但前面最后一段的页数仍然比某个人多，会不会违反"前面的人少抄"？不会，因为"前面的人少抄"是相对于同样最优值下的其他方案而言的，不是要求绝对页数递增。只要在所有可行方案里，你是让前面的人抄得最少的那一类，就满足了题意。

6. 举一反三：这类题的通用套路

6.1 二分答案类题的三大判别特征

以后你再拿到一道题，怎么判断它是不是二分答案题？我总结了三个特征，只要中了两个，基本就可以往二分方向想。第一，题目问的是"最大值最小"或"最小值最大"，比如"让最慢的人最快""让最短的一段尽量长"。第二，答案具有明显的单调性，某个值可行，比它宽松的值一定也可行。第三，题目规模通常不小，正向枚举或 DP 会超时，逼着你用对数级别的方法去逼近答案。

"复制书稿"这三个特征全中，所以它是二分答案的教科书级范例。洛谷 P1182 数列分段也是同款——把一段数列分成不超过 M 段，让每段和的最大值最小，几乎和这题一模一样，只是少了输出方案的麻烦。这类题的通用框架就是：确定二分对象、确定可行边界、写 check 贪心、二分收敛、按需构造方案。把这五步刻在脑子里，遇到同族题就能快速上手。

6.2 从这道题能带走的通用思维

抛开代码本身，这道题真正训练的是两种思维。第一种是把最优化问题转成可行性判定：与其直接求"最小是多少"，不如问"某