★ FEATURED ARTICLE 数列分段放在C语言练习题里是一道看起来非常“入门友好”的题给一串正整数按顺序切成几段每段加起来不能超过给定上限问最少切成几段。我第一次在OJ上看到这题时心里想的是“数组遍历加个判断不就行了”结果连交三次都错在边界数据上后来才意识到自己连题干里的“连续”两个字都没真正读进去。如果你正在学C语言或者准备PAT、洛谷这类入门题库这篇就把这题从题目解读、贪心思路、代码实现到调试排错全部拆开讲一遍顺带把VSCode里配置C/C环境后常见的编译问题也提一嘴。1. 先搞清楚“数列分段”考的是算法还是C语言语法1.1 题目长什么样输入输出与数据范围先看标准描述。输入第一行两个正整数 N 和 M第二行有 N 个正整数 A_i。要求把这 N 个数按原来的顺序分成若干“连续段”也就是每一段在数列里必须是连在一起的不能跳着取也不能把顺序打乱。每一段内部所有数的和不能超过 M。输出最少能分成多少段。比如 N6M10数列是 4 2 7 1 5 3。一种分法是 [4,2] [7,1] [5,3]三段还能不能更少[4,2] [7,1,5] 不行71513[4,2,7] 也不行42713。所以答案是 3。有的题目里会直接把这个“最少段数”称为 Section这也是洛谷 P1181 的经典问法。输入输出格式在大多数 OJ 上是这样输入 6 10 4 2 7 1 5 3 输出 3数据范围通常给到 N 100000A_i 和 M 都可能比较大这一点非常关键后面专门讲类型选择时会用到。这个题名义上是 C 语言数组和循环练习题实际上真正考的是“贪心思维”只不过用 C 语言实现起来特别简短所以很多人容易低估它。1.2 为什么很多初学者第一反应是前缀和或回溯我刚学 C 语言的时候看到“连续段”三个字第一反应是前缀和把前缀和数组 pre[i] 算出来然后枚举所有可能的切点组合看哪些切点满足段和不超过 M再从中选一个切点最多的方案。没错这种思路能求出正确答案但它是指数级的每个数之间都可能切或不切切点组合有 2^(N-1) 种只要 N 超过 30 就完全跑不动。OJ 里 N 经常给到 100000这种思路连样例都过不了。还有同学会想用回溯或者动态规划。动态规划确实可以做dp[i] 表示前 i 个数最少能分几段转移时枚举最后一段的起点 j状态转移大概是 dp[i] min(dp[j] 1)条件是 j1 到 i 这一段的和不超过 M。这个思路本身没有错但时间复杂度是 O(N^2)N100000 时同样会超时而且实现起来比贪心复杂太多。这道题放在 C 语言入门阶段真正的意图是让你发现一个规律因为所有数都是正整数从左往右扫描时每一段总是“能不放就不切”才是最划算的。这个规律没有前缀和那么绕也不需要动态规划只要想明白一次代码就非常简单。1.3 一个反直觉的结论不需要数组也能做对这道题真正巧妙的地方在于你根本不需要把整个数列全部读进数组。因为分段是从左往右连续切的决定“下一段从哪里开始”的只有当前这一段的累加和以及下一个数。只要维护两个变量——当前段的和 sum、已经封口的段数 cnt就可以在输入的同一遍循环里把答案算出来。我第一次意识到这点时对“数据规模决定算法”有了非常直观的感受。用数组当然也没错只是浪费内存而且对初学阶段理解“在线处理”这个概念没有帮助。如果题目要求把所有数都存下来再做N100000 时开 int a[100005] 也没问题但这题的约束和特性决定了边读边算反而是最自然、最不容易出错的写法。后面我给的完整代码就是这种不存数组的版本。2. 从左往右贪心这个策略凭什么是最优2.1 贪心策略的精确表述贪心策略一句话从左往右扫描只要当前数能放进当前段就放进当前段一旦放进去之后当前段和会超过 M就先把当前段封口段数加一再让这个数作为新一段的第一个数。用伪代码描述就是sum 0, cnt 0 for each x in 数列: if sum x M: cnt cnt 1 sum x else: sum sum x 最后输出 cnt 1这里“封口”指的是当前段已经不能再放更多数了必须结束。注意封口之后 sum 不是清零而是直接变成 x因为 x 已经作为新一段的第一个元素放入了新段。这个细节非常容易写错稍后代码部分专门强调。2.2 用反证法证明贪心最优我知道很多人看到“贪心”两个字就头疼总觉得贪心是靠直觉蒙的。但这一题的正确性是可以用反证法严格说明的。假设我们从左到右扫描在某个位置遇到了第一个放不进去的数 x此时当前段的和是 sum且 sum x M。任意一个合法方案中x 都不可能接到当前段后面因为接上之后这段和就超过 M 了。所以在任何一个合法方案里x 都只能作为新一段的起点。既然所有合法方案都在这里做了同一个选择那我们把当前段封口并把 x 当作下一段开头就不会比最优方案差。接着把扫描位置移动到 x 之后的数问题就变成了一个更短的后缀子问题。归纳下去每一步贪心选择都和某个全局最优方案一致因此最终得到的段数就是最少的。这个证明很简洁但它是理解这题的关键不是靠“感觉”蒙答案。2.3 等于 M 的那个瞬间别手滑很多初学者容易在判断条件上犯一个隐蔽错误把 if (sum x M) 写成 if (sum x M)。这两个只差一个等号结果却不一样。实际数段时如果 sum x 恰好等于 M那 x 放进当前段是合法的不应该封口一旦封口段数就会无谓地多 1。举个极端例子M5数列是 3 2 4。用 判断325 不封口sum5下一次 545 封口cnt1sum4最后 cnt12正确。用 判断325 立刻封口cnt1sum2接着 245 又封口cnt2最后输出 3错。这个例子我每次讲都会让人自己跑一遍因为很多人在笔试里不是不会贪心而是败在这种边界条件的“手滑”上。3. 可直接抄的 C 语言实现变量、读入、输出3.1 变量类型为什么必须用 long long这个题的数据范围在不同 OJ 上不完全一样但常见的坑是 M 和 A_i 都可能很大。如果按习惯用 int 存 M 和 sumsum 累加后一旦超过 2147483647 就会溢出变成负数然后判断 sum x M 直接失效。所以我的建议是M 和 sum 一律用 long longx 也读成 long long只有 n 和 cnt 用 int。为什么 cnt 可以用 int因为段数最多也就是 N 段N 通常不超过 100000int 足够。但和值不一样段内累加可能超过 int 上限这是很多人忽略的点。我见过太多人在这个题上吃 32 位整数的亏所以宁可多写几个 long long也不要在类型上抠门。变量类型理由nint元素个数一般不超过 100000Mlong long上限可能很大用 int 会溢出sumlong long每段累加和也可能超过 intxlong long每个数读入时用 %lldcntint段数最多为 nint 足够3.2 完整代码与逐行注释这里我习惯把 cnt 初始化为 0表示已经封口完成的完整段数。每遇到一次放不下就说明当前段被迫结束cnt。扫描完之后最后一段还没计数所以输出 cnt 1。这个初始化的好处是不容易把“最后一段”忘掉也不容易出现多 1 的问题。#include stdio.h int main(void) { int n, cnt 0; long long M, sum 0, x; // 读入 N 和 M if (scanf(%d %lld, n, M) ! 2) { return 1; } for (int i 0; i n; i) { scanf(%lld, x); // 如果某个数本身超过 M题目无法满足按题目要求处理 if (x M) { printf(-1\n); return 0; } // 放进去会超过上限必须封口 if (sum x M) { cnt; // 当前这一段结束 sum x; // x 是新一段的开头也是它当前的累计和 } else { sum x; // 还能放下先放进来 } } // 最后一段还没有被封口要补上 printf(%d\n, cnt 1); return 0; }如果题目保证所有 A_i 都小于等于 M那 x M 的判断可以删掉。但留着它并不影响数据合法时的结果反而能让你在本地测试异常数据时快速发现输入有问题。注意这里的 sum x 不是清零而是把新段的起点值赋给 sum很多初学同学在这一行写成 sum 0结果下一轮把 x 丢掉整个累加逻辑就乱了。3.3 手写几个测试用例确保一遍过我每次写完代码都会先用小数据手算一遍。下面这几个用例是我固定会跑的它们覆盖了单元素、恰好等于 M、连续触发封口等情况输入期望输出说明1 10 / 51单个数直接算一段1 3 / 5-1单个数超过上限无解5 10 / 5 5 5 5 53每两个 5 一段55105 8 / 4 4 1 2 2244 一段122 一段6 10 / 4 2 7 1 5 33题目原始样例用这些用例跑通过之后再提交到 OJ 我心里就有底了。尤其是第二个用例很多题解不会处理但你在本地写防御性代码时一定要考虑它。4. 我调试这个题时踩过的坑4.1 最后一段有没有计数少 1 和多 1 的根源我最开始写的时候是 cnt 0循环里遇到放不下就 cnt循环结束后直接 printf(%d, cnt)结果样例总是少 1。原因很简单最后一段还没有被封口当然不会被 cnt 统计到。后来改成输出 cnt 1 就对了。也有同学反过来cnt 初始化成 1最后又输出 cnt 1这种就会多 1。这种错误很难用肉眼看出来因为样例数据通常比较短有时碰巧能对上。我后来给自己定了一个规则cnt 表示“已经完整结束的段数”循环结束时最后一段一定还没结束所以必须补 1。想清楚语义之后这个坑就再也没踩过。4.2 long long 的格式化符号在不同编译器下的表现另一个坑是 scanf/printf 的格式符。读 long long 要用 %lld如果 M 用 int 而 sum 用 long long读入 M 用 %dsum 用 %lld混着用容易错。在 Windows 上的某些编译器、特别是老版 VC 里long long 可能要用 %I64d。我用 VSCode 配 MinGW-w64 时%lld 是没问题的但如果你在电脑上用 Visual Studio 或者某些在线 IDE要注意这一点。为了避免麻烦我写代码时统一用 long long 和 %lld只在 printf(%d, cnt 1) 那里用 %d。另外开编译器警告也很重要VSCode 里配置 C/C 环境时加上 -Wall 参数如果 scanf 格式符写错编译器通常会给出 warning能帮你省下不少调试时间。4.3 用 printf 和 GDB 观察 sum 与 cnt 的变化如果样例对了但提交错了我建议先别急着改先用 printf 把自己的思路打印出来。比如在 if (sum x M) 前后插入printf(before: cnt%d sum%lld x%lld\n, cnt, sum, x); // 执行封口或累加 printf(after: cnt%d sum%lld\n, cnt, sum);跑一遍小样例立刻就能看出来封口时机对不对。GDB 也可以编译时加 -g 参数然后 gdb 单步执行分别打印 sum、cnt、x。我当年第一次用 GDB 就是在这个题上练的比看书强太多。对于 N 取到十万的数据只靠眼睛看肯定不行但用工具观察几个关键变量问题会很快暴露。4.4 输入里有某个数本身就大于 M 怎么办最后说一个很多人会忽略的情况如果输入里有某个数 A_i M题目是永远无法满足的因为单独把它作为一段段和已经大于 M。洛谷经典版通常保证 A_i M所以很多题解没提。但如果你在别的 OJ 或练习系统里遇到需要按题目要求输出 -1 或者提示无解。我在代码里加了 if (x M) 的判断它不影响数据合法时的结果反而是防御式编程的好习惯。面试或笔试时这种对异常输入的考虑往往能体现你比只会背模板的人更细心。5. 从这题延伸出去两类必刷的变体5.1 数列分段 II固定段数二分答案这题还有个进阶版本常见叫法 Section II给定 N 个数要求正好分成 M 段求“所有段中段和的最大值”最小是多少。这个就不能贪心直接扫一遍了因为段数固定目标是让最长的那一段尽量短。标准解法是二分答案猜一个最大值上限 limit然后用贪心从左到右分段看能不能在不超过 limit 的前提下分出不超过 M 段如果能说明 limit 可以再小一点否则要调大。check 函数的逻辑和基础版几乎一样写出来很清爽int can(long long limit, int n, long long a[], int m) { int cnt 1; long long sum 0; for (int i 0; i n; i) { if (a[i] limit) return 0; if (sum a[i] limit) { cnt; sum a[i]; } else { sum a[i]; } } return cnt m; }主函数里的二分范围就是 max(a_i) 到 sum(a_i)下限取数组最大值上限取总和。如果你能独立写出这个 check 函数说明你对基础版的理解已经到位了。5.2 如果去掉“保持原顺序”会变成什么题如果题目去掉“保持原顺序”这个限制允许你把数列重新排列再分段那就变成另一道题了给定若干数的重量要用尽量少的箱子每个箱子容量 M。这就是装箱问题贪心不一定最优可能需要排序后从大到小放甚至要用动态规划或搜索。所以在读题时一定要辨别清楚“连续分段”是这道题能贪心的根基。一旦“连续”两个字没了解法可能完全不同。这个辨析对初学者特别重要因为很多人在面试时拿到变体题第一反应还是套原来的代码结果肯定不对。5.3 我的练习建议怎么才算真正掌握我的建议是先手写 3 遍基础版一遍用数组存一遍在线处理一遍写成函数返回段数。然后去刷 Section II尝试用二分 check 解决。自检标准很简单能不能在 5 分钟内写出无 bug 的基础版代码能不能用自己的话解释为什么从左往右贪心不会错。如果能这个知识点基本就扎实了。写完基础版之后我还会让自己在纸上把几种边界情况列出来单元素、所有元素和刚好等于 M、存在某个数等于 M、连续触发封口。每次手算完再提交通过率会高很多。最后分享一个我自己的习惯写完这道题后我会把判断条件 if (sum x M) 和输出 printf(%d\n, cnt 1) 这两行抄在便利贴上。别看这题简单这两个地方恰恰是初学 C 语言最容易丢分的位置。另外在 VSCode 里配置好 C/C 环境后记得打开编译器警告选项 -Wall一个看似不起眼的 warning 往往能帮你提前发现类型不匹配的问题。数列分段只是入门题但它把贪心、边界条件、数据类型、调试技巧全串在了一起值得你认真对待一次。
阅读完成 · 觉得有帮助？
