信息学奥赛一本通 1278 的【例9.22】复制书稿(book)跟洛谷 P1281 书的复制是同一道题的两套题面。我头一回在洛谷上刷到它的时候还挺不屑把 m 本书分给 k 个人抄让抄得最多的那位尽量少抄这不就是个平均分吗结果样例直接把我按在地上摩擦。后来才想明白这道题真正卡人的地方有两处一是分给同一个人的书必须连续这一条把所有排序类的贪心全部判了死刑二是它既考最小化最大值的判定思路又考多解时方案怎么还原前者是二分答案的看家本领后者是划分型动态规划的经典套路。我建议把它当模板题来啃因为一旦吃透后面碰到数列分段Monthly Expense这种题基本就是换汤不换药。下面我按自己当时的思路走向把模型翻译、两种写法、输出细节和边界坑从头到尾捋一遍。1. 别急着写转移方程先把复制书稿翻译成一道划分题1.1 题面的三个硬约束决定了它注定是什么模型把题面先摊开看。有 m 本按顺序排好的书第 i 本有 p[i] 页有 k 个人来抄每个人抄写速度一样。约束一共三条第一一本书不能拆开给两个人抄也就是说每本书必须整体归属某一个人第二分给同一个人的书在序列上必须是连续的一段第三所有人的工作量取最大值我们要让这个最大值尽可能小。前两条约束一摆出来其实答案的形状就已经被限死了。因为书本身有序而且不许打乱所以一个合法的分配方案本质上就是把序列切成 k 段连续的区间每一段交给一个人。这时候你手里的操作只有一件事选 k-1 个切点。切点选在哪儿决定了每一段的长度和页数和。第三条约束则决定了目标函数。注意它不是让总页数最小——总页数是个定值所有方案都一样它要的是 min-max也就是让最累的那个人尽可能轻松。这两个目标天差地别。如果是最小化总和那随便切都行谁多谁少无所谓而 min-max 逼着你把重活摊匀还要处理有一段实在匀不开的情况。1.2 为什么排序后贪心平均分一定会挂新手最容易掉进的坑是看到让最多的人尽量少就本能地想把书按页数排个序然后依次丢给当前最闲的那个人不就行了这套多路平衡的贪心在调度问题里确实常见但在这题里它从根上就是错的原因很直接——书有固定顺序不允许重排。举个能一眼看穿的例子三本书页数是 [10, 1, 1]k2。如果允许排序你会把 10 单独给一个人另外两本给另一个最大值是 10。但书必须按原序连续分配合法的切法只有两种切成 [10] 和 [1,1]最大 10或者切成 [10,1] 和 [1]最大 11。最优解是 10恰好等于排序贪心的结果看不出差别。那换 [1, 10, 1]k2切法有 [1] | [10,1] 得 11[1,10] | [1] 得 11。最优是 11。而如果允许重排[10] 和 [1,1] 能压到 10。差别就出来了。所以连续这两个字直接把问题从自由分组降级成了序列划分。这个降级非常关键它让问题的解空间从组合爆炸变成了 O(m 选 k-1) 个切点同时把局部最优的贪心彻底堵死逼你用全局的方法来解。1.3 两个题面在马甲之下的那点差异多解怎么选一本通 1278 和洛谷 P1281 的主体完全一致输入都是第一行 m 和 k第二行 m 个页数输出都是 k 行、每行两个整数表示某个人抄的起始书号和结束书号、且起始编号从小到大排列。真正的差别落在多解的处理上。当最优的最大值固定之后往往不止一种切法能达到这个值。比如 [3, 4, 5, 3]k2最优最大值是 8切法就一种[3,4] 和 [5,3]但像 [2,2,2,2,2]、k3最优最大值是 4可以切成 [2,2] [2,2] [2]也可以切成 [2] [2,2] [2,2]两个方案的最大值都是 4可输出的区间完全不一样。这时候题目一般会加一句限定让编号靠前的人抄得尽量少。这句话翻译成操作语言就是——把书尽量往后面压让前面的人越轻越好。理解这一点至关重要因为它直接决定了方案还原时你从哪一头开始贪心。如果你从前往后贪心得到的会是前面的人尽量多抄的方案答案对但输出错一交就是满屏红。我在这个问题上白交过好几次印象太深了。2. 二分答案这条路把最小化最大值改造成一次判定2.1 单调性的来源为什么这件事可以二分min-max 类问题有一个几乎万能的开局把求最小的最大值改成判定某个最大值 x 行不行。这道题的判定问题是这样的——假设规定每个人最多只能抄 x 页k 个人够不够把这 m 本书抄完能这么做的前提是单调性如果 x 可行那么任何比 x 大的 x 也一定可行因为上界放宽了原本合法的划法依然合法。反过来如果 x 不可行那比它小的更不可能可行。可行性关于 x 单调二分的地基就稳了。二分的下界取所有书里最厚的那本max p[i]因为再小连一本都抄不完上界取所有书的页数总和因为让一个人全抄必然可行。在这段区间上找最小的可行 x就是最终答案里那个抄得最多的人的工作量。2.2 check 函数要守住的三条线判定函数是整个二分法的核心也是我见过最多人写错的地方。我一般让它守住三条线第一单本超限直接否决。如果某本书的页数本身就大于 x那无论怎么分都超限直接返回 false。这条判断其实可以提前到二分开始之前把下界设成 max(p[i]) 就顺手解决了但写在 check 里更保险。第二从左往右贪心地数人数。维护一个当前累计页数 sum遇到下一本如果能塞进去sum p[i] x就塞塞不下就开新的一段把人数加一、sum 重置为当前这本书。这一段贪心之所以正确是因为在固定上界 x 的前提下让当前这个人尽量多抄、绝不浪费容量能让总段数最少。段数最少意味着最省人。第三把人数的判断写成cnt k。注意是小于等于。如果算出来只需要 3 个人而你手里有 5 个人那是可行的——多出来的人可以分到更细的段里反正每本书本身都不超界继续往下拆永远拆得动。把这三条缝在一起check 的时间是 O(m)套一层二分后总复杂度是 O(m log(sum))面对几百甚至几万的数据量都绰绰有余。2.3 从后往前还原让前面的人抄得少落地二分只能告诉你最优的最大值 X还原不出具体方案得单独做一次构造。这里的贪心方向是固定的从最后一本书往前扫。每一轮处理一个人从第 k 个人倒着处理到第 1 个人让这个人从当前位置往前尽可能地多吃书只要累计页数不超过 X 就继续往前吞吞到加不进去为止。因为是从队尾往队头吃越靠后的人吃到的书越多前面剩下的人自然就轻松了正好对应前面的人抄得尽量少。这里有一个细节千万别漏不能把书吃光得给前面还没处理的人每人至少留一本。所以循环条件里要加一个位置判定保证当前位置还够减。如果漏了这条你会得到一堆空区间比如输出3 2这种起点大于终点的诡异结果样例都过不去。我写这段的固定骨架是这样的C#include bits/stdc.h using namespace std; const int MAXN 505; int m, k; long long p[MAXN]; // 判断若每人最多抄 x 页k 个人能否抄完 bool check(long long x) { int cnt 0; long long sum 0; for (int i 1; i m; i) { if (p[i] x) return false; // 单本都抄不完 if (sum p[i] x) { sum p[i]; // 塞进当前段 } else { cnt; // 开新段 sum p[i]; } } if (sum 0) cnt; return cnt k; // 用的人不超过 k 即可 } int main() { scanf(%d %d, m, k); long long lo 0, hi 0; for (int i 1; i m; i) { scanf(%lld, p[i]); hi p[i]; lo max(lo, p[i]); } long long x hi; // 二分最小可行上界 while (lo hi) { long long mid lo (hi - lo) / 2; if (check(mid)) { x mid; hi mid - 1; } else lo mid 1; } vectorpairint,int ans(k 1); int pos m; // 从最后一本书往前吃 for (int person k; person 1; person--) { int end pos; long long sum 0; // 位置 pos person 保证前面每个人至少留一本书 while (pos 1 pos person sum p[pos] x) { sum p[pos]; pos--; } ans[person] {pos 1, end}; } for (int i 1; i k; i) printf(%d %d\n, ans[i].first, ans[i].second); return 0; }2.4 几个运行细节代码对了不代表能过第一页数要用long long。虽然大多数版本的测试点页数不大但总和有可能溢出 int尤其当你把 hi 设成总和又想稳妥一点的时候long long 是最省心的选择。第二二分的写法建议用x mid; hi mid - 1这种记录可行解再往左逼的模式不要用lo mid那种容易死循环的变体。我早期用过while (lo hi) { mid (lo hi) 1; if (check(mid)) hi mid; else lo mid 1; }这个也正确但下界必须初始化成可行值一旦写成 0 又恰好 check(0) 返回 false就会空转。第三还原时那个pos person的判断等价说法是已经吃了 books前面还剩 person-1 个人、至少要留 person-1 本书所以 pos-1 person-1。两种写法都对看哪个顺眼用哪个。3. 划分型 DP 视角f[i][j] 枚举的是最后一个人抄了哪一段3.1 状态设计把前 i 本分给 j 个人二分答案很优雅但这题在很多教材里是放在划分型动态规划这一章的一本通 1278 也不例外。所以这套DP写法必须会它也是理解这类问题本质的最短路径。状态定义我一般写成f[i][j]把前 i 本书分给前 j 个人在最优划分下最累的那个人的工作量。目标就是f[m][k]。为什么是前 i 本而不是任意 i 本因为书有序前面的人拿的必然是前缀里的一段后面的人拿后缀天然形成前缀结构。这个状态定义等于承认了分配是从左到右依次切段这件事。3.2 转移方程枚举最后一个人到底抄了哪几本想清楚第 j 个人也就是最后一个被安排的人做了什么转移就出来了。假设他抄的是从第 i-t1 本到第 i 本这连续的 t 本那么前面 j-1 个人负责前 i-t 本他们的最大工作量是f[i-t][j-1]第 j 个人自己的工作量是这段区间的页数和记作sum(i-t1, i)这一划分方案的整体最大值是两者取 max。我们要在所有可能的 t 里挑最小的那个于是f[i][j] min over t of max( f[i-t][j-1], sum(i-t1, i) )t 的取值范围很关键。下界是 1因为每个人至少得抄一本上界是i - (j - 1)因为前面 j-1 个人每人至少一本得给它们留够 j-1 本。所以 t 从 1 枚举到 i-j1。这一步很多人的代码会漏掉上界导致前面的人被分到 0 本书状态里出现 f[x][j-1] 而 x j-1 的非法情况答案偏大。复杂度是 O(k · m²)空间是 O(k · m)。在 m ≤ 500 的规模下最坏约 1.25 亿次内层操作朴素实现能过但有点悬加个前缀和把区间求和压成 O(1) 就非常稳了。3.3 初始化那两个最容易写反的边界DP 的初始化是这题的另一处高发翻车点。规则很简单f[0][0] 0前 0 本书分给 0 个人最大值当然是 0f[i][0] INFi 0书还没分完但人已经没有了这是非法状态标成无穷大f[0][j] 0j 0其实也成立——没有书要抄多少人都是 0 工作量。代码里我通常只显式处理前两条第三条因为内层枚举 t 从 1 开始、i 从 j 开始循环压根不会碰到 f[0][j] 这个状态所以可以省略。但如果你把 i 的循环起点写成 0就一定要补上不然转移里会读到脏值。另外要注意只有当 i j 时 f[i][j] 才有意义因为 j 个人每人至少要一本书。所以外层 j 从 1 到 k内层 i 从 j 到 m这个循环顺序不能反。反了的话你会用到还没算出来的 f[i][j-1]同一行的左边结果是错的。核心代码长这样const int MAXN 505; const long long INF 1e18; long long p[MAXN], pre[MAXN]; long long f[MAXN][MAXN]; // 读入后建立前缀和 for (int i 1; i m; i) pre[i] pre[i-1] p[i]; for (int i 1; i m; i) f[i][0] INF; f[0][0] 0; for (int j 1; j k; j) { for (int i j; i m; i) { // 至少 j 本书才分得开 f[i][j] INF; for (int t 1; t i - j 1; t) { // 最后一人抄 t 本 long long cur max(f[i-t][j-1], pre[i] - pre[i-t]); f[i][j] min(f[i][j], cur); } } } // 答案就是 f[m][k]3.4 DP 版的方案还原思路和二分版是同一套算出f[m][k] X之后还原方案依然是从后往前扫只不过判定标准从和不超过 X变成了切出来的这段和不超过 X并且剩下的前缀能由剩下的人搞定。为了保证这一点做法和 2.3 节几乎一模一样从第 m 本开始往前吃能塞就塞塞到超 X 或者前面的人不够分书为止。有人会想用 DP 数组回溯从f[m][k]出发找一个 t 使得max(f[m-t][k-1], sum) f[m][k]跳到f[m-t][k-1]继续。这样做也对但有个坑——可能有多个 t 都满足等式选错方向就会得到前面的人抄得多的那种方案。我的建议是别绕了直接用从后往前的贪心还原既短又不依赖 DP 数组里的具体取值和二分版共用一段代码维护成本最低。4. 对拍与极限用例这道题真正容易翻车的地方4.1 输出格式区间顺序、行数、空格这题的输出格式要求比我预想的严格。k 行每行两个整数第一个是起始书号、第二个是结束书号而且这 k 行的起始编号必须从小到大排。也就是说第 1 行对应第 1 个人拿最前面的那几本第 k 行对应最后一个人。因为我们是从后往前还原、倒着填ans[person]最后顺序输出就自然满足了。常见的格式错有两种一是把区间写成结束在前、起始在后触发 WA二是拿 C 的cin/cout逐行输出但忘了换行符或者中间多打了空格。我的习惯是用printf(%d %d\n, l, r)一个格式符管到底不给自己挖坑。还有一点是行数。就算某个人一本书都没分到k 大于实际需要的人数时会出现题面一般还是要求输出 k 行。不过主流版本都保证了 k ≤ m真到每人至少一本所以只要你把给前面留够书这个约束守死就不会出现空区间。4.2 贪心方向这是全题最容易反的一个地方我前面反复强调从后往前贪心是因为从前往后贪心的坑实在太隐蔽了。设想你用二分求出 X8然后从第 1 本书开始往后扫能塞就塞塞到超 8 为止得到的是前面的人尽量多抄的方案。它的最大值确实也是 8完全最优但输出的区间和答案对不上——因为题目要的是前面的人尽量少抄。我当时的做法是拿两个手写小样例对着候选方案一遍遍比对才彻底记住方向。这里给一个心算验证法如果输出里前几行的区间都很短比如第一个人只抄了两三本那方向八成是对的如果第一个人抄了一大段、后面几行越来越短那基本就是反了。4.3 几类必须手测的极端数据光过样例是不够的这几类数据我每次都会手动跑一遍用例输入要点期望行为k 1只有一个人输出一行区间是整段 [1, m]k m一人一本每行区间长度都是 1起点依次递增单本超大某本页数远大于其他二分下界自动抬到它不会被拆开全相等所有页数一样验证多解时输出的是前面少抄那个含零页页数为 0贪心不应把它当成塞不下而误开新段第三行的单本超大特别值得说。如果忘记把二分的下界设成 max(p[i])而是从 0 或从某个均值起步check 会在遇到这本书时返回 false二分区间可能收敛到错误的值最后输出一个明显超界的方案。我见过的错误答案里这一条占了大头。第四行的全相等是检验多解方向的试金石。比如 5 本书页数全为 2、k3最优最大值是 4。正确输出应该是1 2、3 4、5 5把书往后压而不是1 1、2 3、4 5把书往前压。虽然两者最大值都是 4但只有前者符合题意。4.4 用暴力枚举做对拍比空想边界靠谱数据范围小的时候暴力是最好的裁判。m 不超过 10 左右时可以枚举所有选 k-1 个切点的组合算出每种划分的最大值取最小值然后在所有达到最小值的方案里挑前面的人抄得少的那个输出出来。把它当标准答案跟你自己的二分版或 DP 版随机造几十组数据对拍一旦不一致就能立刻定位问题。对拍脚本我一般这么写造数据的程序随机生成 m、k 和每本书页数页数控制在 1 到 20 之间方便触发各种临界跑一次标准答案和一次自己的解diff 一下。while (diff)挂着跑个几分钟比盯着代码看有效得多。尤其是转换思路的时候比如从 DP 版切到二分版对拍能帮你抓住那些样例看不出来、但数据一大就露馅的逻辑漏洞。5. 这套模板还能接着打从 P1281 延伸出去的同类题5.1 最大值最小家族数列分段是最近的亲戚搞明白这题之后你会发现数列分段洛谷 P1182几乎是同一个人换了个说法。它问的是把长度为 n 的正整数数列分成不超过 m 段使各段和的最大值最小。你看连目标函数都一模一样唯一的差别是 P1182 不要求输出具体方案只输出那个最小的最大值。所以 P1182 可以只用二分答案的那一半——写个 check 数段数二分出答案就收工不用碰方案还原。反过来说如果你 P1182 写得顺那 P1281 的难点就全落在还原方案上了。我习惯把这两道题连着做先练判定和二分再练还原把 min-max 这条线打通。5.2 什么时候二分答案不够用必须请出 DP二分答案 贪心判定看着万能其实有个前提判定过程必须能用局部贪心解决。这题能满足是因为约束只有段和不超过 x这一条贪心地让当前段尽量满就是最优的。但一旦目标函数变复杂比如要求各段的某种加权代价之和最小或者段数必须恰好等于 k 且每段代价非线性局部贪心就不再正确了这时候只能回到 DP。这也是为什么一本通把它放在划分型 DP 章节——它在教你识别贪心能救和贪心救不了的分界线。DP 版的通用性更强代价是复杂度高一个量级数据一大就吃力。我把两者的差异列个表方便你按数据规模选对比项二分答案 从后往前贪心划分型 DP时间复杂度O(m log(sum))O(k · m²)空间复杂度O(m)O(k · m)适用数据规模m、k 可到 1e5 量级m ≤ 500 左右方案还原天然支持从后往前扫即可需要额外回溯容易选错方向思维门槛低但边界容易写错高状态和初始化都要想清5.3 我个人的选型习惯实战里我基本是这样分流的只要目标是最小化某段的和的最大值、且段的约束是和不得超过上界这种单调判定我一律优先写二分答案因为它代码短、复现快、还不怕数据大。只有当题目加了额外的维度比如每段还有额外代价、或者要求段数恰好为 k 且代价模型不是简单的求和再取 max我才会切到 DP。回到这道题本身我推荐的练习顺序是先用 DP 把模型吃透理解划分这件事到底在枚举什么再用二分答案重写一遍体会判定思维怎么把 O(k·m²) 压到 O(m log(sum))最后把两版的方案还原统一成从后往前贪心确保多解时的方向绝对正确。走完这一圈min-max 这类题基本就长在你手上了。最后分享一个我自己的小习惯每次写完还原逻辑我都会拿km一人一本和全相等页数这两组数据各跑一遍眼看着输出从最后一行往前一行行变短方向对了心里才踏实。这个习惯帮我省掉了不少提交次数也希望它能帮你少走点弯路。