这道题我在某大厂的OD机考C卷里碰到过两次准确说是同一个同学考了两次两次都挂在“书籍叠放”上。第一次没读懂题第二次看懂了但是输出顺序反了。这题在LeetCode上能找到几乎一样的原型俄罗斯套娃信封但OD机考的版本多了“严格小于”和“按编号输出叠放顺序”两个坑导致很多人在本地跑样例没问题一提交就WA。今天我把它彻底拆开讲一遍从题目怎么读、状态怎么定义、Java代码怎么写到双机位考试的实战配合、提交前怎么自查全部塞进这篇文章里。适合三类人正在刷题准备OD机考的人、想搞懂LIS变体的人、以及单纯想看看机考题到底长什么样的人。1. 题目解读与考点定位1.1 原题描述与样例分析书籍叠放是这么个事有n本书每本书都给出长和宽长大于等于宽书A能放在书B上面当且仅当A的长严格小于B的长且A的宽严格小于B的宽。注意是“严格小于”和A的长等于B的长这种case绝对不能算可叠放。现在让你求出一摞书的最大数量并且输出一种可行的叠放顺序从上往下输出书的编号。输入格式一般是先给一个整数n接下来n行每行两个整数表示长和宽。部分版本还会给一个编号1到n也有版本用输入顺序当编号。C卷这道题要求输出编号所以输入顺序就默认是编号顺序。样例通常长这样5 10 5 8 4 12 9 7 3 9 6上面的样例里能叠出最多4本第2本(8,4)放第5本(9,6)上第5本(9,6)放第1本(10,5)上。等一下这里(9,6)的长宽分别是9和6第1本是(10,5)宽度5小于6但第5本宽度6大于第1本宽度5所以第5本不能放第1本上面。正确的叠法其实可以从(7,3) → (8,4) → (9,6) → (12,9)这样4本从上到下输出就应该是4 2 5 3 4注意输出顺序是从上到下不是从下到上。很多人在这一步把顺序搞反样例全对交上去全WA。1.2 这一题到底在考你什么表面上是“叠书”实际上是三个算法考点的套娃偏序关系建模、排序降维、最长上升子序列LIS变体。先说偏序关系。两个元素书之间要满足“长和宽同时严格小于”才能建立叠放关系这本质上是一个二维偏序问题。二维偏序的问题通常有两条路一是用树状数组/CDQ分治这类数据结构去做二是想办法排序把它降成一维。机考场景下第一条路过于复杂第二条路才是正解。然后是排序降维。你先按长升序宽度降序排好序再去看宽度序列会发现“是否能叠放”的问题完全等价于在宽度序列上找最长严格递增子序列。这个转化是整道题的灵魂后面我会用一个完整的表格把排序前后的变化捋清楚。最后是路径输出。大部分LIS题目只要求输出最大长度这道题却要求输出具体方案这意味着你需要额外维护一个pre数组前驱指针来做回溯。这个考点看起来很细但其实就是动态规划里“记录转移来源”的标准操作理解了之后反而不难。2. 算法思路与复杂度分析2.1 先排序把二维问题压成一维的关键一步我给你说个场景你就能明白为什么要排序。假设你面前有一堆书你要找“最大叠放数量”如果直接暴力组合每本书要判断能不能放在另一本上面这是O(n^2)的图遍历问题遇到1000本书就一定超时。但如果把所有书按长从小到大排好叠放关系的判断就变成了“只看宽度”。排序的具体规则是第一关键字按长度升序第二关键字按宽度降序。为什么宽度要降序看安排长度相同的时候这两本书是不能叠放的因为长相等不满足严格小于。如果宽度升序那么遍历到后面那本同样的书时它的宽度比前面的大宽度序列上会形成一个“上升”可能触发一次错误的状态转移。把宽度降序排列后同一长度的书在宽度序列上是下降的天然阻挡了它们之间发生转移。用上面的样例来演示书本原本顺序是编号长度宽度11052843129473596排序之后变成编号长度宽度47328459611053129注意看编号1的顺序比编号5靠后虽然它的长度(10)大于编号5(9)但宽度5小于6。在排序序列里它就是“乱入”的这正是为什么排序后不能只比较宽度其实还要注意在原始排序里长度已经保证了非降序只有在长度相等时才需要靠宽度降序来阻隔。对于严格递增的LIS长度非降序时如果宽度严格递增那长度一定严格递增吗并不一定因为可能长度相等且宽度递增但有序后同长度宽度是降序所以不会发生。所以只要排序写对了宽度序列上跑LIS就是完全安全的。2.2 状态定义与转移方程排序完成后问题变成了在宽度序列w[1..n]上求最长严格递增子序列的长度并记录路径。经典的动态规划做法如下dp[i]表示以第i个位置为“最下面那本书”时能叠出的最大数量。注意我强调的是“最下面”这样想的好处是转移的时候只需要考虑哪些书能放在我上面也就是找宽度更小的位置然后max 1。转移方程dp[i] max(dp[j] 1)其中1 j i且w[j] w[i]。同时用pre[i]记录这个最大值是从哪个j转移过来的。如果dp[i]1说明没有可转移的书pre[i]-1。最终答案就是max(dp[i])而输出路径是从那个最优的i开始往回链pre把编号逆序收集再反转成从上到下的顺序输出。这里还有一个细节排序之后书的编号丢了怎么办所以给每本书一个id字段排序时带上id最后输出用id而不是排序后的下标。举例推演一下上表排序后宽度序列是[3,4,6,5,9]。初始化dp全为1pre全为-1。i1w3dp[1]1。i2w4j1时w[1]34dp[2]dp[1]12pre[2]1。i3w6j1、2都满足max是dp[2]13pre[3]2。i4w5j1、2满足dp[2]13pre[4]2。i5w9j1、2、3、4都满足max是dp[3]14pre[5]3。所以最大长度是4对应的终点是第5个位置的“书”排序后第5个对应编号3号长12宽9。回溯pre链5→3→2→1对应编号是3,5,2,4再反转就是从上往下4,2,5,3和前面分析一致。2.3 复杂度分析与选型O(n^2)的DP两层循环每层n次总时间复杂度O(n^2)空间复杂度O(n)。OD机考C卷的n通常不超过1000O(n^2)毫无压力甚至可以跑n5000都勉强能过。如果想优化到O(n log n)可以用经典的贪心二分维护一个tails数组把LIS长度求出来但问题是输出路径就变得极麻烦需要维护“每个长度的最小结尾索引”之类的额外结构在机考的紧张环境下非常容易写错。我的建议是拿到这题先用O(n^2)写把所有边界都测过去如果题目明确说n最大是10^5才考虑优化。机考要的是稳定AC不是秀复杂度。3. Java实现与核心代码3.1 完整代码可直接运行直接给一份我实测过、能通过样例和封闭测试的Java代码。注意我用了BufferedReader做输入比Scanner快路径回溯用了Deque双端队列方便最后一次性按从上到下顺序输出。import java.io.*; import java.util.*; public class Main { static class Book { int len; // 长 int wid; // 宽 int id; // 原始编号 Book(int len, int wid, int id) { this.len len; this.wid wid; this.id id; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); ListBook list new ArrayList(); for (int i 0; i n; i) { StringTokenizer st new StringTokenizer(br.readLine()); int len Integer.parseInt(st.nextToken()); int wid Integer.parseInt(st.nextToken()); list.add(new Book(len, wid, i 1)); // 输入顺序就是编号 } // 排序长度升序宽度降序 list.sort((a, b) - { if (a.len ! b.len) { return Integer.compare(a.len, b.len); } return Integer.compare(b.wid, a.wid); }); int[] dp new int[n]; int[] pre new int[n]; Arrays.fill(dp, 1); Arrays.fill(pre, -1); int best 0; // 最优终点下标 int bestLen 1; for (int i 0; i n; i) { for (int j 0; j i; j) { // 由于排序这里宽度严格小于就足够安全 if (list.get(j).wid list.get(i).wid dp[j] 1 dp[i]) { dp[i] dp[j] 1; pre[i] j; } } if (dp[i] bestLen) { bestLen dp[i]; best i; } } // 回溯路径注意这里得到的是从下到上的顺序 DequeInteger stack new ArrayDeque(); int cur best; while (cur ! -1) { stack.push(list.get(cur).id); // push到头部最后poll就是从上往下 cur pre[cur]; } System.out.println(bestLen); while (!stack.isEmpty()) { System.out.print(stack.poll()); if (!stack.isEmpty()) { System.out.print( ); } } System.out.println(); } }3.2 核心代码段拆解先看排序这段。Comparator里用了Integer.compare避免返回可能溢出的差值。这里如果长度相同就按宽度降序这样同长度的书在宽度序列上是递减排列绝不会产生合法的叠放转移。这段逻辑是本题最容易出错的地方一定要理解后再敲。再看dp转移这段。内层循环从0到i-1判断list.get(j).wid list.get(i).wid。这里不需要再判断长度因为排序已经保证了长升序并且同长度时的宽度降序已经封堵了同长度的转移路径。这一点非常关键如果你在转移条件里加上长度严格小于的判断也没有错但那就没必要排序宽度降序了。我的这份代码为了清晰故意只在宽度上判断让LIS逻辑更纯粹。路径回溯用的Deque。可以先按pre链从终点一路回溯到起点得到的是从下到上的顺序然后用push方法把它反转为从上到下。这里如果直接用ArrayList收集再Collections.reverse也一样看个人习惯。3.3 本地编译与运行测试我用样例跑一遍输入 5 10 5 8 4 12 9 7 3 9 6 输出 4 4 2 5 3和期望一致。再拿几个极端case测试输入只有1本书1 6 3输出1 1这里有唯一一本书只能叠1本。输入所有书尺寸完全相同3 5 5 5 5 5 5排序后宽度序列是降序[5,5,5]LIS长度只有1。这时候输出哪本书的编号取决于排序后的第一个也就是原输入中的哪一本。边界case在OD机考的测试里经常出现务必手动验一遍。4. 双机位OD机考实战经验4.1 双机位是什么意思环节怎么配合双机位说白了就是考试时有前置和后置两个摄像头或者电脑摄像头加上一部手机从侧后方对着你的屏幕和手部区域监考画面全程录制。这个设置主要是为了防作弊电脑端摄像头拍你的脸手机端摄像头拍你桌面和屏幕。实际考试时设备调试很耽误时间。我的建议是提前40分钟进考场环境把手机支架摆好确保能拍到键盘区域和半张屏幕。拍摄角度不要太远也不要太近远了怕识别不了键盘动作近了怕反光让屏幕看都看不清。如果考试中途画面掉线不要慌举手线下或在系统里发消息线上等监考处理自己继续写代码。有些同学一掉线就反复重启设备反而浪费答题时间。考试前一定要把手机调成勿扰模式一切推送通知全部关掉。我就见过有同学考试到一半手机弹了个消息被系统判了画面异常。这个不算作弊但会打断状态而且解释起来非常浪费时间。4.2 答题策略这道题该花多少时间C卷一般有3道编程题难度递增。书籍叠放往往是第二题或者第三题的难度定位中档偏上。整体考试时间是120分钟左右我建议这样分配审题5分钟专门确认三件事编号从几开始、输出是压顺序还是从下到上、长和宽是否有“严格小于”的限制。这三件事每一样都会直接决定你是否AC。然后快速搭建模板10-15分钟把输入输出框架敲好算法核心20分钟测试用例10分钟留20分钟缓冲处理意外情况。总计大约60分钟能稳定拿下这题。如果做了30分钟还没有任何进展别再死磕。先蒙一个靠谱的写法比如直接输出所有书按宽度从小到大排的编号性能不稳定但至少有一半概率能对几个点。机考是有部分得分的不要空着交白卷。另外考试时别急着一次性写完整段代码。先写排序打印出来看一眼顺序对不对再写dp打印dp数组验证转移是否正确。在本地IDE里调试没问题再粘贴到答题区。有些同学会直接写到答题区里调试一旦语法报错要来回切窗口心态很容易崩。4.3 输入输出处理的机考细节OD机考的代码模板会给一个Main类只需要把你自己的代码填进去。注意两点一是类名必须是Main二是不要带package声明。我和身边几个同学都犯过这个错本地能跑一提交就编译失败。输入这块我建议直接用BufferedReaderStringTokenizer不要用Scanner。别看Scanner方便在数据量达到几千行的时候速度差距能到好几倍。尤其这题如果n给到5000、一万用Scanner在在线评测环境里确实容易卡到超时。代码里读取那几行直接复制上面给的模板就行。还有输出格式不要有额外的空格或者换行。最后一本书的编号输出之后不要跟空格直接换行。我用Deque的poll方法每次输出完检查一下是否为空再决定是否加空格就是干这个的。另外一个非常重要的细节很多在线评测系统对输入行尾的空格很宽容但对空行很苛刻。如果读入时遇到空行你用了br.readLine()会得到空字符串此时转换成int会直接抛异常。稳妥做法是先trim()再判断是否为空。上面代码里我用了trim()和split空格但没有对空行做直接判断因为题目的输入约定里不会出现空行。如果担心可以加一个while循环跳过空行成本不高。5. 常见踩坑与避坑指南5.1 五个高频WA原因第一个坑把“严格小于”写成了“小于等于”。长或宽相等的两本书是不允许叠放的一旦用了所有尺寸相同的书都会被当成可以叠结果长度直接虚高。这个错误在样例规模小的时候很难发现因为样例刚好没有相等尺寸。第二个坑同长度的书被错误转移。即使你用了LIS如果没有对宽度做降序处理会导致同样的长被连起来叠输出长度就多了一截。这一点是我自己第一次做题时的翻车现场后来加了宽度降序就稳了。第三个坑输出顺序反了。题面会明明白白写着“从上到下”但很多人dp做出来之后习惯直接从终点往前输出正好就是从下到上。建议在本地测试时手动验证一下输出顺序能不能对应到叠放顺序上。第四个坑编号从0开始。很多程序员习惯了数组下标0基输出的时候直接println(i)而不是i1导致编号全错。这个错误不体现在长度上只体现在编号上特别隐蔽。第五个坑长宽输入顺序搞反。有些题的输入是“长 宽”有些是“宽 长”甚至有些版本直接在每行写成“宽 长”。你写Book的时候要把两个字段的语义彻底绑定清楚。下面给一个高频问题的速查表症状可能原因解决办法结果长度多1用判断可叠放改为同长书被叠在一起宽度没降序排序第二关键字改降序长度正确但编号乱输出前没按id映射输出list.get(idx).id运行超时Scanner输入慢 / O(n^2)超数据换BufferedReader或考虑优化dp本地正常提交编译错类名不是Main / 有package类名改Main删package5.2 边界数据测试清单在提交前我强烈建议你用这几组数据自测一遍。它们结构单一但能暴露绝大多数问题。场景输入示例期望输出单本书15 511全部相同35 55 55 511任意编号乱序49 18 27 36 444 3 2 1长度全同35 35 15 211任意反向升降41 102 93 84 724 3或任意一对最后一个反向升降的例子要注意长升序但宽度降序LIS长度可能只有2因为宽度逆序。这就是为什么不能只贪心去找“最长宽度子序列”而要在宽度上找严格上升子序列。5.3 同类题型与扩展思路书籍叠放不是孤例它在LeetCode里是“俄罗斯套娃信封问题”在算法竞赛模板里是“嵌套矩形求最长路径”在ACM里还有“木棒加工”的变体。它们的核心都是二维偏序 LIS/贪心但考察点略有区别。俄罗斯套娃信封问题多了一个条件宽度相等也不能叠和这里的严格小于一模一样解法直接通用。嵌套矩形问题往往要求输出最大嵌套链的长度但给的是复杂的有向图如果用拓扑排序加动态规划复杂度会高一些而先排序再LIS的思路可以直接套。木棒加工问题是很多时候用贪心做因为它求的是“最少加工批次”而不是“最长链”你要优先排序然后对宽度做贪心分组。一句话总结遇到两个属性长和宽、货币金额和数量、时间和长度等等都必须满足严格上升关系的题第一反应应该是“能不能先按一个属性排序然后转化为另一个属性上的LIS”。如果能就固定住这个套路模板不费脑子。6. 提交前最后一遍自查清单我每次做这类题时间快到时都会按照这个顺序检查代码第一步检查排序规则长度升序 宽度降序compare方法里有没有写反。写反了的话同长度问题会直接暴露成WA而且非常难查。第二步检查转移条件list.get(j).wid list.get(i).wid不带等号。屏幕上有没有不小心留一个 。第三步检查输出映射stack里放的是list.get(cur).id不是下标。因为下标已经排过序直接输出下标别人看到的会是一串和原编号无关的数。第四步检查类名和输入输出类名Main没有package输出最后有一个换行。这三项任何一项出错都是整题0分。第五步心算一个极端case所有书尺寸相同答案必须是1而不是n。如果跑出来是1说明排序和转移在“严格小于”上没有问题。这套自查流程走完基本上这题就是稳定的得分点。我从第一次做这道题时的WA到后来考试稳定AC靠的就是把排序和严格小于这两件事钉死在代码里。尤其是宽度降序这一手你理解它为什么要降序就再也不会在黄卷上摔第二回。这里再分享一个小技巧考试紧张的时候状态定义不清会把dp[i]想成“到第i本为止的最大数量”但那样写出来的状态转移会变得很混乱。我自己经验还是把dp[i]锚定为“以第i本作为最底下那本的最大叠放数量”这样每次转移其实是在“找更多书放在它上面”思路特别通顺。你刷题刷多了就会发现很多LIS类问题把“结尾元素”还是“当前元素”定义清楚代码能差出一大截。如果后续你还想深挖可以试试把这题的排序换成按长降序、宽降序看看DP逻辑需要怎么调整这种举一反三的练习对机考帮助很大。祝刷题顺利考场稳定发挥。