1. 先把题面读透这到底是个什么模型1.1 题目在讲一件什么事“复制书稿”在《信息学奥赛一本通》里是第 1278 号标着“例9.22”洛谷上对应编号 P1281名字叫“书的复制”。两个 OJ 的题面几乎是同一份先给两个整数 m 和 k再给 m 本书各自的页数要求把这 m 本书按原有顺序切成 k 段每段交给一个人去抄最后让抄得最多的那个人抄的页数尽可能小并且输出每个人负责的书的起止编号。注意这里有个硬约束——顺序不能打乱。书是排好队的一摞第 3 本书必须和第 4 本书挨在一起你不能把第 5 本抽出来塞给第 1 个人。这个约束直接把问题从“把总数平均分”这种小学数学题变成了一个区间划分问题。很多人第一眼会想把总页数除以 k 不就完了真去写就会发现根本对不上因为书是不可切割的每本书的页数是整数你可能刚好卡在某个边界上多一本就超、少一本就不够。这道题被编排在动态规划那一章所以绝大多数同学第一反应是去设f[i][j]表示前 i 本书交给 j 个人抄、最大工作量的最小值。思路没错但写起来又慢又难调转移的时候要枚举最后一段的长度复杂度是 O(m²k)m 和 k 都可能到 500算下来上亿次操作常压不太好过。更要命的是DP 只能算出最优值还得回头把方案还原出来而题目要求的方案还带一个字典序条件还原过程中很容易写错。我个人的经验是这道题最舒服的做法是二分答案 倒序贪心。二分负责求“最小的最大工作量”倒序贪心负责输出符合题目要求的方案。两段代码都短逻辑清晰调试成本极低。下面我把这条路从头到尾拆开讲包括每个参数为什么这么取、每一行为什么这么写以及我自己踩过的几个坑。1.2 为什么“均分”思路一定会翻车假设 m3k2三本书的页数分别是 5、1、5。总页数是 11平均下来每个人 5.5 页。如果你按这个思路硬凑会得到“一个人抄 5 页、另一个人抄 6 页”的目标看起来很美。可行吗你只能把书切成两段连续区间切法只有两种[5] | [1,5]工作量是 5 和 6或者[5,1] | [5]工作量是 6 和 5。两种切法的最大工作量都是 6而理论下界是 5.5 上取整等于 6刚好能碰到。这个例子算运气好。换个例子m3k2页数 5、8、3。总共 16平均值 8。切法[5] | [8,3]得 5 和 11最大 11[5,8] | [3]得 13 和 3最大 13。最优是 11而平均值算出来的 8 根本达不到。原因很简单那本 8 页的书没法拆开谁拿到它谁就得抄满 8 页再配上旁边的书很容易就冲到两位数。所以这道题真正的核心不是“怎么分得平均”而是“在保证每段都不超过某个上限的前提下能不能用不超过 k 个人抄完”。一旦把问题这样反过来问答案的单调性就出来了二分的框架也就顺理成章。1.3 两种解法的取舍把两种思路摆在一起对比取舍就很清楚了。维度区间 DP二分答案 贪心时间复杂度O(m²k)最坏约 1.25 亿O(m log(sum))约 500×13空间复杂度O(mk) 或滚动后 O(m)O(m)方案输出需要额外回溯边界多一遍倒序扫描搞定代码量60 行以上40 行左右调试难度转移下标极易写错主要坑集中在切分条件表格里能明显看出二分方案在效率和实现难度上都占优。DP 唯一的优势是“套路更正统”如果你在备考时想练区间划分的 DP 手感写一遍也无妨但比赛或者刷题的时候没有理由不用二分。我在下面第四章也会把 DP 的写法附上方便你对照理解但主线还是走二分。2. 二分答案的根基单调性从哪来2.1 把问题改写成判定题二分答案的核心思想是把“求最小值”这种优化问题换成一个“给定上限问行不行”的判定问题。具体到这道题就是我们不再直接问“最小的最大工作量是多少”而是问假设每个人最多只能抄 lim 页那么能不能用不超过 k 个人把 m 本书按顺序全部抄完这个判定问题非常好回答。从左往右扫一遍书一边扫一边累加当前这个人的页数一旦加上下一本会超过 lim就让这个人收工换下一个人从这本书重新开始累加同时把用掉的人数加一。扫完之后如果总人数不超过 k就说明 lim 可行否则不可行。为什么这个贪心是对的因为“每段尽量往长了吃”是让段数最少的策略。段数最少都超过 k 了那任何别的切法只会更碎、人数更多。反过来如果最少段数不超过 k那说明 lim 可行我们总可以把某几段再拆开凑够 k 个人前提是 k 不超过 m每段至少留一本书。这一点在后面讲方案输出时会反复用到先记住结论。2.2 单调性证明与二分边界的确定单调性是这样的如果上限 lim 可行那么 lim1 一定可行。理由非常直白——原来那套切分方案在 lim 下每段都不超过 lim自然也不超过 lim1所以同一套方案在 lim1 下同样合法。既然“可行”这个性质一旦成立就永远成立它就在数轴上形成了一条分界线左边全不可行右边全可行我们只要用二分找到这条线的右端点就是最小的可行值。二分边界的取法有讲究这是我见过最容易出错的地方之一。下界lo取max(a[i])也就是页数最多的那本书。为什么不能更小因为无论怎么分总得有一个人拿到这本书他一个人的工作量就至少是这本书的页数所以答案不可能小于单本最大页数。上界hi取所有书页数之和sum对应“所有书都给一个人抄”的极端情况显然可行。如果想再紧一点下界可以取max(max(a[i]), ceil(sum/k))因为按总数平均下来最大工作量至少是平均数上取整。这个优化不是必须的但能让二分少迭代几次。别小看这点优化有些题卡常数的时候它就是救命的。二分的写法用标准的“找最小可行值”模板while (lo hi)当check(mid)为真时记录答案并往左收hi mid - 1否则往右推lo mid 1。循环结束时记录的那个值就是答案。这个模板比while (lo hi)的写法安全不容易在边界上死循环我个人强烈推荐。2.3 check 函数的实现细节check 函数看着简单其实有两个细节必须注意。第一个是数据类型。如果题目给的页数较大累加的时候可能溢出 int所以求和变量建议用long long。二分的mid也会在sum的范围内如果 sum 接近 int 上限lo hi也可能溢出稳妥的做法是写mid lo (hi - lo) / 2。这是老生常谈但每年都有人栽在这上面。第二个是初始计数的处理。很多人的循环写成“每次超了就 cnt”结果初始化 cnt0最后判断cnt k就过了但遇到某些边界会差一个人。我的建议是初始化cnt 1代表“至少有一个人在用”扫到超限时才 cnt这样语义更清楚也不容易数错。还有一个小陷阱如果某一本书的页数本身就大于 lim那么这个 lim 直接不可行check 应该立刻返回 false。不过因为我们把下界设成了单本最大值这种情况在二分过程中不会出现所以省掉这个判断也没关系。但如果你偷懒把下界设成 0 或者 1那就必须加这一条否则会算出错误的答案。3. 输出方案为什么必须倒着贪心3.1 正序贪心错在哪很多人求出最优值之后顺手就用 check 里的那段正序逻辑把方案打出来——从左往右分每段尽量长。值是对的但方案往往过不了因为题目对方案有一个额外的字典序要求在最大工作量最小的前提下让第一个人抄得尽量少然后第二个人尽量少以此类推。我们拿 5、1、5、k2 这组数据看。最优值是 6。正序贪心会怎么分第一段尽量长——516不超再加 5 就超了所以第一段是[1,2]第二段是[3,3]。结果是第一个人 6 页。倒着分呢最后一个人尽量多抄——516不超所以最后一段是[2,3]前面剩[1,1]第一个人只抄 5 页。同样是 6 的最大值倒序方案让第一个人少抄了 1 页这才符合题目的要求。把这件事说透题目要的是字典序最小的方案先压第一个人的工作量再压第二个……正序贪心恰好把重量都堆在了前面方向完全反了。3.2 倒序贪心的逻辑拆解倒序贪心的做法是从最后一本书开始从右往左扫描让当前的这个人尽量多抄。具体实现上有两种等价写法一种是先确定每个人的区间从右往左推另一种是先算出每段的右端点再翻转输出。我用的是后者逻辑更顺。扫描时维护三个变量sum表示当前这一段已经累计的页数right表示当前这一段的右端点p表示还没确定任务的人数包括当前正在填的这一段所属的那个人。每遇到一本新书a[i]判断两件事如果把这本书加进来sum a[i]超过了 lim那这一段就到头了把[i1, right]作为一段记录下来然后让这本书另起一段如果剩下的书数 i 已经不足以让剩下的每个人至少分到一本也就是i p - 1那也必须切否则前面的人就得空着手。这两个条件合起来就能保证每一段都不超过 lim同时每个人至少有一本书。我第一次写的时候只写了第一个条件结果遇到书数和人数相等的极端数据就崩了输出少一行这点后面第四章会再展开。3.3 一个容易被忽略的条件刚才提到的第二个条件很多人会忽略甚至有些题解里也写得含糊。它的本质是题目要求输出 k 行也就是 k 个人都得有活干。如果只按“超限才切”来分很有可能分出来的段数小于 k前面几个人就没书抄了方案就废了。i p - 1这个条件是怎么来的扫描到第 i 本书的时候还剩 i 本书第 1 到第 i 本没有归属同时还有 p 个人没被分配。注意这里 p 包含了当前正在填的这个人。要让 p 个人都有书抄至少要 p 本书而剩下的只有 i 本。如果i p - 1说明再不给当前这个人收尾剩下的书就不够分了所以必须在当前位置切一刀。切完之后剩下 i 本书给 p-1 个人此时i p - 1正好一人一本后面每一步都会触发切分段数自然就补齐到 k 了。这个条件的妙处在于它和“超限才切”并不冲突——如果 lim 是最优值两个条件触发的时机不会打架。顺带说一句洛谷 P1281 的一个特殊情况如果 k 大于 m也就是人比书还多洛谷的题面里要求先输出若干空行。大多数测试数据保证 k ≤ m但如果你遇到这种数据就得在最前面补上k-m个空行。这一点务必看题面确认别照着别的题解抄完就交。4. 完整代码与逐段讲解4.1 C 实现下面这份代码是我自己用的版本测试过洛谷 P1281 和一本通 1278两边都能 AC。#include bits/stdc.h using namespace std; int m, k; int a[505]; int L[505], R[505]; // 记录每段的起止 // 判定每人上限为 lim 时能否用不超过 k 个人抄完 bool check(long long lim) { int cnt 1; // 至少需要一个人 long long sum 0; // 当前这个人的累计页数 for (int i 1; i m; i) { if (a[i] lim) return false; // 单本就超了直接不可行 if (sum a[i] lim) { cnt; // 换下一个人 sum a[i]; // 这本书归新人 } else { sum a[i]; // 继续累加 } } return cnt k; } int main() { scanf(%d %d, m, k); long long total 0; int mx 0; for (int i 1; i m; i) { scanf(%d, a[i]); total a[i]; mx max(mx, a[i]); } // 二分最小的可行上限 long long lo mx, hi total, best total; while (lo hi) { long long mid lo (hi - lo) / 2; if (check(mid)) { best mid; hi mid - 1; } else { lo mid 1; } } // 倒序贪心还原方案让前面的人尽量少抄 int lim (int)best; int cnt 0; // 已划分的段数 int p k; // 还没分配的人数 int right m; // 当前段右端点 long long sum 0; // 当前段累计 for (int i m; i 1; --i) { // 条件一加上这本书会超限 // 条件二剩下的书不够剩下的人一人一本 if (sum a[i] lim || i p - 1) { L[cnt] i 1; R[cnt] right; cnt; --p; right i; sum a[i]; } else { sum a[i]; } } // 最后一段最前面那一段别忘收尾 L[cnt] 1; R[cnt] right; cnt; // 倒序记录翻回来输出 for (int i cnt - 1; i 0; --i) { printf(%d %d\n, L[i], R[i]); } return 0; }几个关键点我单独拎出来说。第一个是check里的if (a[i] lim) return false;。因为我们把下界设成了单本最大值这一句理论上永远不会触发但留着它有好处万一你后面改了二分下界的写法比如为了练手把 lo 设成 0这行代码能帮你兜住。这叫防御性编程多写一行没什么成本。第二个是二分的best变量。它记录“最后一个让 check 返回 true 的 mid”。因为我们是往左收的所以它最终就是最小可行值。有人喜欢不加 best循环结束后直接输出 lo这样在“找最小可行值”的模板下 lo 恰好是答案但稍微改动一下模板就错了。加一个 best 语义更明确出错概率低很多。第三个是倒序输出的部分。我先用数组正着存下来再用for (int i cnt - 1; i 0; --i)反着打印。这样保证输出的顺序是从第一个人到最后一个人。如果你当场就用栈或者反向遍历打印逻辑也等价但数组更容易调试——发现答案错了的时候可以直接把整个数组打出来看。4.2 Python 版本洛谷的在线 IDE 支持多种语言如果你习惯用 Python下面这版可以直接用。注意 Python 的递归和循环开销比 C 大但 m 只有 500完全够用。import sys def main(): data sys.stdin.read().split() idx 0 m int(data[idx]); idx 1 k int(data[idx]); idx 1 a [0] * (m 1) total 0 mx 0 for i in range(1, m 1): a[i] int(data[idx]); idx 1 total a[i] mx max(mx, a[i]) def check(lim): cnt 1 s 0 for i in range(1, m 1): if a[i] lim: return False if s a[i] lim: cnt 1 s a[i] else: s a[i] return cnt k lo, hi, best mx, total, total while lo hi: mid (lo hi) // 2 if check(mid): best mid hi mid - 1 else: lo mid 1 lim best segs [] p k right m s 0 for i in range(m, 0, -1): if s a[i] lim or i p - 1: segs.append((i 1, right)) p - 1 right i s a[i] else: s a[i] segs.append((1, right)) segs.reverse() out [] for l, r in segs: out.append(f{l} {r}) sys.stdout.write(\n.join(out) \n) main()Python 版本里我把输入用sys.stdin.read().split()一次性读进来这样比逐行input()快很多。洛谷的评测机对 Python 的时间限制比较宽容但养成批量读入的习惯总没坏处数据量大的题能救你一命。4.3 区间 DP 的写法参考如果你想对照着看 DP 是怎么做的下面给出核心转移。设f[i][j]表示前 i 本书分给 j 个人时最大工作量的最小值pre[i]是页数前缀和。// 初始化 memset(f, 0x3f, sizeof(f)); f[0][0] 0; for (int j 1; j k; j) { for (int i j; i m; i) { // 前 i 本书分给 j 个人至少 j 本 for (int t j - 1; t i; t) { // 前 t 本分给 j-1 个人 int seg pre[i] - pre[t]; // 最后一段的页数 f[i][j] min(f[i][j], max(f[t][j - 1], seg)); } } } // 答案是 f[m][k]这套转移的正确性没问题问题出在方案输出。因为f里存的只是最优值你要还原方案就得从f[m][k]往前倒推每次找是谁转移过来的。而在倒推的时候如果同时想满足“让前面的人抄得少”这个字典序条件判断会变得很绕——你得保证在最优值相同的前提下选起点最靠右的那一段。很多人 DP 写对了值方案却过不了就是卡在这里。所以我再强调一次这道题的最佳实践就是二分加倒序贪心DP 只适合用来练手或者做理解上的补充。别为了“正统”两个字跟自己的调试时间过不去。5. 调试实录那些年踩过的坑5.1 高频错误对照表这道题看着简单坑却不少。我把我和身边同学踩过的坑整理成一张表你写完之后可以逐条对一遍。现象根因修正方式答案偏大二分下界设成 0 或 1check没判单本超限下界改成max(a[i])或补上a[i] lim判断输出少一行只写了超限切分没写i p - 1补上“剩余书数与人数相等”的切分条件前后顺序颠倒倒序扫描后忘记翻转输出存进数组后从后往前打印后半段为空切分时机偏早最后一段没收尾循环结束后手动补上[1, right]结果随机变化累加用 int 溢出求和变量换成long long局部通过整体挂边界数据里 k 等于 m 或 k 等于 1单独造这两类数据测一遍表格里最需要重视的是第二行和第四行。前者是逻辑漏洞后者是纯粹的粗心。我建议你在写完倒序部分之后先拿 km 和 k1 这两组极端数据跑一遍能瞬间暴露大部分问题。5.2 对拍脚本与手造数据如果你不确定自己的写法对不对最靠谱的方式不是盯着代码看而是对拍。写一个暴力程序枚举所有切分位置直接算出最优值和最优方案。虽然复杂度爆炸但 m 只要不超过 10暴力完全跑得动。对拍脚本的大致思路是写一个随机数据生成器随机生成 m 在 1 到 10 之间、k 在 1 到 m 之间、每本书页数在 1 到 20 之间的数据然后分别跑暴力程序和你自己的程序比较输出是否完全一致。只要跑上几百组不出问题基本就可以放心提交了。手造数据也有几个必测的套路。第一组是 k1也就是所有人抄同一份稿子答案是总页数输出一行。第二组是 km每本书一个人答案是单本最大值输出 m 行。第三组是页数全都相等比如全是 3这种数据能测出切分的均匀程度。第四组是有一本书特别厚比如页数是 1、1、100、1、1这种数据最容易暴露上界和下界的问题。5.3 一个真实的翻车案例我第一次写这道题的时候check 里写的判断是return cnt k;而不是cnt k。当时我想的是“反正二分到最后段数一定正好等于 k用等号没区别”。结果死活过不了。问题出在哪在二分的过程中cnt k和cnt k对可行性的判断是不一致的。举例来说假设某个 lim 下最优分段是 3 段而 k 等于 5。用cnt k判断这个 lim 会被判成不可行于是二分继续往右推最后算出来的答案就偏大了好几倍。用cnt k才对因为段数少于 k 的时候我们完全可以再把某些段拆细凑够 k 个人。这件事给我的教训是可行性判定一定要写清楚“可行”的完整定义。在这道题里可行 “能用不超过 k 个人抄完”而不是“恰好用 k 个人抄完”。一字之差答案天差地别。提示写完check之后自己拿几个简单的数字口算一遍。比如 m3、k2、页数是 5、1、5最优答案应该是 6。如果程序输出 11八成是判断写反了。6. 从这道题能带走的通用套路这道题虽然只是信息学奥赛里的一道例题但它背后的两个套路适用范围极广。第一个套路是“最大值最小化”。凡是题目里出现“让最大的那个尽可能小”这种表述你几乎都可以先想二分答案。典型的变体包括把 n 个数分成若干段使每段和的最大值最小、在数轴上摆若干个点使相邻距离的最大值最小、安排任务使最长完工时间最短。识别出这个关键词就成功了一半。第二个套路是“倒序贪心满足字典序”。只要题目要求“在最优解里让越靠前的越优”你大概率可以用倒序处理来搞定。原理是让靠后的部分尽可能多地承担靠前的部分自然就轻了。这个思路在区间划分、任务分配、资源调度里都出现过。最后分享一个小习惯我做这类题的时候会先把check函数单独抽出来用几组手算过的数据验证它的输出。比如页数是 5、1、5k2那么check(5)应该返回 false因为 5 和 6 这两段里有一段是 6check(6)应该返回 true。验证通过之后再写二分和方案输出整个流程会顺很多。调试的时间大部分都花在边界上与其提交之后对着评测结果的“WA”发呆不如在本地把手算过的数据挨个跑一遍这比任何技巧都管用。