看到“识文断句”这四个字估计准备华为OD机试C卷的朋友都会多看一眼。这题不像典型算法题一上来就考你图论或者DP也不像单纯字符串处理那样直接套模板它考的是贪心策略而且是用得比较明显的那种。我第一次在模拟题里碰到它时第一反应是“给古文加标点有什么好考的”结果按从左到右逐个空隙加标点的思路写得分怎么都上不去。后来把计分规则和约束条件抠清楚才发现题目考察的核心是两件事把标点的收益按顺序排好再把不相邻位置的关系处理好合在一起就是一个标准贪心框架。这道题放在C卷100分这一档性价比很高思路通了以后Java实现四五十行就能过。这篇文章我把题面还原、贪心推导、Java落地、边界情况和考试节奏一起讲一遍既适合第一次接触华为OD机试的读者也适合把这题当贪心入门练手。1. 题面还原与计分规则先搞清楚“识文断句”到底在让你做什么1.1 一个常见的题目版本我在刷题和模拟中遇到的版本大致是这样的给出一句不含标点的中文句子全部由汉字组成长度记为 n。然后给出 K 种标点比如逗号、句号、顿号、问号、感叹号等等每种标点都有一个初始分值。现在要求你在句子的任意两个汉字之间插入标点插完以后输出最终的句子。计分规则有几个关键点每种标点可以重复使用但每使用一次这种标点的分值就减 1一直减到 0 或者负值后就不再使用句子的第一个字符之前和最后一个字符之后都不能插入标点任意两个标点之间至少隔着一个汉字也就是说不能出现“某某。某某”这种连续标点的情况。最终得分是所有已插入标点在插入那一刻分值的总和要求输出一种得分最高的方案。这里的分值递减是这题最核心的设计。比如逗号初始 5 分第一次用逗号得 5第二次再用逗号就只能得 4第三次 3以此类推。这个规则直接决定了后面整个贪心策略的走向。1.2 四条约束决定了算法走向把规则拆开看影响算法的其实就是四条空隙数量固定长度为 n 的句子内部空隙是 n-1 个句首句尾不能用。每个空隙最多放一个标点一个位置不可能同时放两个标点这个约束天然存在。相邻空隙互斥第 i 个空隙和第 i1 个空隙不能同时放标点。标点收益衰减同一种标点用得越多后续收益越低。前三条合在一起问题就变成了“在一条长度为 n-1 的路径上选择若干个互不相邻的点”。第四条则是给每个被选中的点赋予一个会变化的权重。一开始我总觉得这个题应该用动态规划毕竟“不相邻选点”听上去就很像线性 DP但仔细想收益衰减和标点种类之间的关系后会发现这道题把权重设计成了“与位置无关、只与标点使用次数有关”这就让贪心策略变得可行了。1.3 一个具体示例走一遍我用一个例子把规则走通。假设句子是“落霞与孤鹜齐飞秋水共长天一色”这是 14 个汉字内部空隙 13 个。标点有逗号 5 分、句号 4 分、顿号 3 分。按规则逗号的收益序列是 5、4、3、2、1句号是 4、3、2、1顿号是 3、2、1。把所有收益展开并排序后前几个是 5逗号、4逗号、4句号、3逗号、3句号、3顿号、2逗号。因为 13 个空隙最多只能选 7 个互不相邻的位置所以要从前 7 个收益里拿 7 个标点放在空隙 0、2、4、6、8、10、12 这些位置。最后输出就是“落霞与孤鹜齐飞秋水共长天一色”。这个断句看起来确实不像正常人写的但机试判分看的是约束和得分不是语文通顺度。我第一次看到这个结果时也愣了两秒后来才意识到题目本身就不要求你按语义断句只要满足计分规则怎么断都行。2. 为什么是贪心策略收益递减与不相邻选点背后的数学直觉2.1 暴力思路为什么劝退很多人看到这题第一反应是枚举所有空隙的放或不放状态每个空隙有“不放、放逗号、放句号、放顿号……”这么多选择总的方案数接近 (K1) 的 n-1 次方。n 稍微大一点比如几十个字这个量级就直接爆炸了。就算用 DP 做状态里还要记录每种标点已经用了多少次因为收益递减依赖使用次数这一下就把状态空间撑大了好几倍。所以必须在“决策”这件事上做简化。题目真正想问的是既然每种标点的收益按使用次数递减那么收益较大的那些插入机会应该在所有空隙里优先被安排。这个想法一旦成型自然就走到了贪心。2.2 标点收益可以展开成一条有序序列每种标点从初始分值开始每用一次减 1直到 0 或者负值这相当于把一个标点拆成多次使用机会每次机会的收益是一个递减的值。比如初始 5 分的逗号可以被拆成收益为 5、4、3、2、1 的五次机会。所有标点都这样展开后就得到了一堆“机会”每个机会带有两个信息这次使用能拿多少分、用哪个标点字符。把所有机会按收益从高到低排序就会得到一个全局的收益序列。这时问题的本质就变成了从头到尾取这个序列里的机会每次取一个机会都要把它放到一个合法空隙里而且已经占用的空隙旁边的空隙不能再放。为什么可以放心地按收益从高到低取因为收益是独立于位置和顺序的。你这次用掉逗号的 5 分机会不影响你后面用句号的 4 分机会也不影响顿号的 3 分机会。收益递减只会让同一个标点后续机会的价值变低但不会让你已经拿到的收益缩水。换句话说先拿高收益的机会永远不亏这就是贪心策略能够成立的根本原因。2.3 相邻约束在路径图上意味着什么空隙可以看成一条路径上的节点第 i 个空隙和第 i1 个空隙之间有一条边。每选择一个节点它左右两个相邻节点都不能再选这就是路径上的最大不相邻集合问题。在路径图上不相邻集合的大小上限是固定的等于节点数除以 2 向上取整。更关键的是对于一条路径从左到右每隔一个节点选一个就能达到这个上限。比如 13 个节点从左到右选 0、2、4、6、8、10、12正好 7 个这就是最大数量。所以位置关系的处理并不复杂按从左到右的顺序扫描空隙遇到一个能放的位置就放一个标点然后跳过下一个位置。这样做得到的数量一定是最多的而且由于收益序列已经排好序每次从这个序列里取的都是当前能拿到的最高收益机会总分自然是最优的。2.4 从左到右放置为什么可行这里有个直觉上的疑问从左到右放会不会因为先占了某个位置导致后面收益更高的机会放不进去不会。因为所有空隙在收益上是同权的标点机会的收益大小只跟“哪个标点、第几次用”有关跟“放在哪个空隙”无关。任何一个空隙都可以放任何标点所以位置之间唯一的区别就是相邻互斥关系。路径图上所有“每隔一个选一个”的方案在数量上都是相等的能放进来的机会数量也一样多。既然数量一样收益序列也只需要按顺序取同样数量的机会那从左到右这种最朴素、最容易被想到的方法就是最优的。这一步想通了代码写起来就非常简单了。3. Java落地方案展开收益序列的简洁实现3.1 数据结构选型核心思路这个解法需要三样东西一个列表存展开后的标点机会每个机会包含收益值和标点字符一个数组记录每个空隙是否已被占用或者被禁用一个字符数组记录每个空隙最终插入的标点。展开标点机会时要注意收益从初始值递减到 1 就行因为收益是 0 或者负数时插入一个标点反而会拉低总分不属于最优解的一部分。展开完成后按收益降序排序。放置阶段从左到右扫描空隙。遇到已经被禁用的空隙就跳过遇到可用的空隙就取一条未使用的标点机会放进去然后把这个空隙自身以及它左右相邻的空隙全部标记为禁用。如果标点机会已经取完直接结束扫描。3.2 可运行Java代码下面是我实际调试过的一版代码注释写得比较全直接贴到牛客网类的 Java 提交模板里就能跑。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.nextLine().trim(); int n s.length(); int k Integer.parseInt(sc.nextLine().trim()); Listint[] marks new ArrayList(); // 元素: {初始分值, 标点字符} for (int i 0; i k; i) { String[] parts sc.nextLine().trim().split(\\s); char ch parts[0].charAt(0); int score Integer.parseInt(parts[1]); marks.add(new int[]{score, ch}); } // 将每个标点展开成多次机会机会的收益 当前分值逐次减 1 Listint[] seq new ArrayList(); // 元素: {收益, 标点字符} for (int[] m : marks) { for (int cur m[0]; cur 0; cur--) { seq.add(new int[]{cur, m[1]}); } } // 按收益降序排列收益相同则保持稳定即可 seq.sort((a, b) - b[0] - a[0]); // inserted[i] 表示第 i 个空隙插入的标点0 表示不插入 char[] inserted new char[Math.max(0, n - 1)]; boolean[] banned new boolean[Math.max(0, n - 1)]; int seqIdx 0; for (int pos 0; pos n - 1 seqIdx seq.size(); pos) { if (banned[pos]) continue; inserted[pos] (char) seq.get(seqIdx)[1]; seqIdx; banned[pos] true; if (pos - 1 0) banned[pos - 1] true; if (pos 1 n - 1) banned[pos 1] true; } StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { sb.append(s.charAt(i)); if (i n - 1 inserted[i] ! 0) { sb.append(inserted[i]); } } System.out.println(sb.toString()); } }这段代码有几个地方值得展开说明一下。banned 数组初始全是 false。每次放置标点后把当前空隙自身标记为 true再把左右相邻空隙也标记为 true这样后面扫描到相邻空隙时会直接跳过。这是“相邻空隙不能同时放标点”这个约束最直接的表达。seq 列表就是贪心所需要的全局收益序列。排序是整个过程最重要的一步它保证了每次取出的机会都是当前可用机会里收益最高的。收益相同的标点谁先谁后无所谓因为总收益不变输出方案只要是合法最优之一就能通过。3.3 代码里几个容易被忽略的细节第一个细节是“收益为 0 的标点机会不要放进去”。我一开始在展开时用了 cur 0导致收益为 0 的机会也进了序列排序后排在最后面最后如果空隙还有富余就会把一个得 0 分的标点插到句子里。虽然 0 分不影响总分的“最大化”但在某些判题版本里会被当作无意义输出而且万一原题允许负收益这样做会直接扣分。所以展开时一定要用 cur 0 作为循环条件。第二个细节是“扫描空隙时不能 break”。有人在 for 循环里写“if (banned[pos]) break”这是错误的。banned 只代表某个空隙被禁用不代表后面的空隙都不能用。比如空隙 0 被占用后空隙 1 被禁用但空隙 2 仍然是可用的必须继续扫描下去否则会漏掉大量可放置的位置导致总标点数不够多。第三个细节是 seqIdx 和 pos 的关系。seqIdx 表示已使用了多少条标点机会pos 表示当前扫描到第几个空隙。这两个变量的增长完全独立因为收益高的机会并不一定必须放在靠前的空隙里只要它被放到任意一个合法空隙就行。用独立的 seqIdx 计数器从头到尾消费收益序列正好体现了“先取全局最高收益机会”的贪心思想。4. 如果题目变体改了优先队列方案和其他模型适配4.1 优先队列版适用于每个空隙收益不同的情况我上面给的展开序列方案依赖一个前提所有空隙在收益上是等权的也就是任意空隙放任意标点的得分都一样。但有些题库里的“识文断句”版本会对不同位置加不同权重比如某些字符后面更适合放句号某些位置只有特定标点可选。遇到这种变体展开序列就没法直接用了。这时候需要用一个优先队列队列里放的是候选对象每个候选包含三个信息空隙位置、标点字符、当前收益。初始化时把所有“空隙位置 × 标点”的组合都丢进队列按收益降序排列。每次从队首取出一个候选先判断这个空隙是否已经被禁用如果被禁用了就跳过如果没被禁用就把它放进去同时禁用相邻空隙。这里要注意某一种标点被使用后它的分值要减 1所以你要更新其他还未禁用的空隙上该标点的收益再把新的候选重新放入队列。这种做法在逻辑上更通用代码量也更大。但是要提醒一句如果每个空隙的收益真的互不相同那么“每次都选当前收益最大的候选”不一定能保证全局最优因为一个高收益位置可能会挡住另外两个中等收益的位置。这时候题目还要求贪心策略能 AC通常意味着数据范围被设计得比较小或者题目背后另有约束保证贪心正确。遇到这种情况我建议在有限时间内先按贪心写跑不过再考虑 DP。4.2 变体一每种标点只能用一次有些版本会规定每种标点只能使用一次这其实就是把收益递减模型的一个特例。因为每种标点只有一次机会展开后的序列就是 K 条收益记录排序后按收益从高到低取即可。这种情况下从左到右放置时可能出现“收益高的标点种类不够多”的情况。比如 13 个空隙能放 7 个标点但 K 只有 3那么最多只能放 3 个标点剩下 4 个空隙空着不插标点。我的代码里 seqIdx 到达 seq.size() 后 for 循环会自动停止所以这个变体完全兼容不需要改动逻辑。4.3 变体二标点数量有限制如果题目改成“最多只能插入 M 个标点”处理方式就是把展开收益序列的长度和 M 取个最小值。M 可能小于最多可放的不相邻位置数也可能大于取完 M 条机会就停止放置。这个变体在我的代码里也只需要改一个地方for 循环的终止条件是 seqIdx seq.size()改成 seqIdx Math.min(seq.size(), M) 就可以。因为收益是正数在只求最大化总分的前提下多放一个标点一定会增加总分所以“最多 M 个”等同于“正好放 M 个”。4.4 变体三某些位置禁用标点有的题目会在输入里额外给出一些位置明确说这些位置不能插入标点比如某些专有名词中间不能断句。这个处理起来也不复杂在初始化 banned 数组时把这些位置先标记成 true再跑同一套从左到右的扫描逻辑就行。这里要注意的是如果你事先禁用了某个位置那么它左右位置仍然可以正常使用不要因为“左右相邻”关系再次误标。设置初始禁用和放置后的禁用是两个独立动作初始禁用的位置不应当影响它邻居的初始状态只有实际放置标点的那一刻才需要把左右邻居同步禁用。5. 边界条件与实测用例这部分才是真正拉开分差的地方5.1 输入层面的坑华为OD机试用的是 ACM 模式核心代码模板里 Scanner 读字符串时最容易被坑的是第一行带 BOM 头。特别是一旦你的代码在本地编辑过或者从网页粘贴测试用例字符串开头可能会带上一个不可见字符。直接用 s.charAt(0) 去当汉字处理一定出问题。稳妥的做法是读完一行之后做一次 trim如果有 BOM可以判断第一个字符的 int 值再手动去掉。另一个坑是全角空格。题目描述里标点字符和分值之间可能用英文空格也可能用中文输入法下的全角空格。如果直接 line.split( ) 按英文空格切分全角空格切不开parts[1] 就会越界。用 split(\s) 能兼容空格和制表符但仍不能兼容全角空格。最稳的方式是把全角空格先替换成英文空格再 split。还有一个不那么起眼的问题是每行结尾的 \r。Windows 环境下的样例文件常常带 \rreadLine 的时候 Scanner 一般能处理但如果遇到以 \r\n 结尾且字符串本身是空格的情况建议统一做 replace(\r, ) 再处理。5.2 输出层面的坑输出要求是在原句子上插入标点不能改变汉字顺序。我用 StringBuilder 拼接时是先追加汉字再判断当前汉字后面那个空隙是否有标点有的话追加标点。这个顺序别搞反也千万别在字符串末尾追加标点因为句尾不允许插入标点。如果题目允许多个最优解输出任意一个都可以。但有些判题系统会要求“按某种固定顺序的任意解”比如优先使用分值高的标点。我的代码已经按收益降序取标点了所以符合这个要求。如果你担心输出方案和标答不同可以看看题目里有没有写“输出任意一个最优解”华为OD大部分题都会写清楚。5.3 几个我实测过的用例我在本地跑了几个用例可以对照验证一下逻辑。第一个最简单的用例输入“甲乙”K1标点为逗号 3。句子只有 2 个汉字空隙 1 个最多只能放 1 个标点。输出“甲乙”。这验证了基本插入逻辑。第二个用例输入“十二月”K2标点为顿号 2、句号 1。句子 3 个汉字空隙 2 个最多选 1 个位置。收益序列排序后是 2顿号、1顿号、1句号取第一条机会输出“十二月”或者“十二月”。哪个位置都合法总收益都是 2。第三个用例是 n1 的单字串比如“春”。这时没有内部空隙inserted 数组长度为 0for 循环不执行直接输出“春”。我在最初版本里没有对 n1 做保护导致 new char[n-1] 创建了长度为 0 的数组没问题但后面 inserted[i] 访问越界。所以在构造数组时用了 Math.max(0, n-1) 来规避。第四个用例专门测收益为 0 的标点。输入“天地”标点为句号 1。展开后只有收益 1 的一次机会放置后输出“天地”。如果某个标点初始分值本来就是 0展开循环直接不执行不会出现在收益序列里输出就保持原句不变。这个行为符合“不插入零分标点”的最优策略。6. C卷考试节奏与实战体会这道题该花多少时间6.1 100分题在整份卷子里的定位华为OD机试的卷子一般有一道 100 分题和一道 200 分题C卷也是如此。100 分题通常不会考特别复杂的算法更多是把一个常见思路包装成一个有点生活化的场景“识文断句”就是典型的把贪心策略包装在中文语境里的题目。它的难点不在代码量而在你能不能快速看出收益递减和相邻互斥这两个关键约束。我的建议是这类题如果能在 20 分钟内完成读题、建模、写码、过样例就已经非常理想了。读题时先把计分规则列成清单约束条件用笔写在草稿纸上不要边读边想代码。很多人在考场上栽在这道题上不是因为不会贪心而是因为读题不够仔细漏掉了“每种标点重复使用会递减”这一句写出来的代码自然就是错的。6.2 双机位环境下的调试习惯C卷考试是双机位前后摄像头都会开着。实际考试的时候虽然监考重点是防作弊但双机位环境对做题心理还是有点影响的你写代码的过程会被录下来反复删改会显得思路不清晰更重要的是第一机位切代码、第二机位切桌面如果你在本地 IDE 和 OJ 页面之间来回切换很容易被误判。所以我个人的习惯是先在草稿纸上把主逻辑想清楚再一次性把代码写到 OJ 编辑器里写完立刻在本地脑补几个边界用例检查一遍最后再点提交。不要依赖反复编译去发现低级错误那样只会浪费时间。尤其像这题这种 40 行不到的代码逻辑清晰比手速重要得多。6.3 给后来人的一点点经验我在刷这道题时踩过的最大的坑其实就是“以为懂了其实只懂了一半”。第一次我按从左到右无脑插标点没有处理相邻禁用的传播结果输出里连续出现两个标点被判非法。第二次我处理了相邻禁用但展开收益时把 0 分机会也算进去了又导致输出末尾多了一个多余标点。第三次才真正把所有细节对齐。如果你也在准备这道题我建议你拿到题面后不要先急着写代码而是先用一个 7 个字的小串把收益序列手写出来然后在纸上模拟一遍放置过程。这个过程只要 3 分钟但对理解贪心顺序的帮助极大。等你把“收益序列排序”和“不相邻位置选取”这两件事彻底想通这道 100 分题基本上就是送分题了。