企业官网建设流程全解析

数列分段，放在C语言练习题里，是一道看起来非常“入门友好”的题：给一串正整数，按顺序切成几段，每段加起来不能超过给定上限，问最少切成几段。我第一次在OJ上看到这题时，心里想的是“数组遍历加个判断不就行了”，结果连交三次都错在边界数据上，后来才意识到自己连题干里的“连续”两个字都没真正读进去。如果你正在学C语言，或者准备PAT、洛谷这类入门题库，这篇就把这题从题目解读、贪心思路、代码实现到调试排错全部拆开讲一遍，顺带把VSCode里配置C/C++环境后常见的编译问题也提一嘴。

1. 先搞清楚“数列分段”考的是算法还是C语言语法

1.1 题目长什么样：输入输出与数据范围

先看标准描述。输入第一行两个正整数 N 和 M，第二行有 N 个正整数 A_i。要求把这 N 个数按原来的顺序分成若干“连续段”，也就是每一段在数列里必须是连在一起的，不能跳着取，也不能把顺序打乱。每一段内部所有数的和不能超过 M。输出最少能分成多少段。

比如 N=6，M=10，数列是 4 2 7 1 5 3。一种分法是 [4,2] [7,1] [5,3]，三段；还能不能更少？[4,2] [7,1,5] 不行，7+1+5=13；[4,2,7] 也不行，4+2+7=13。所以答案是 3。有的题目里会直接把这个“最少段数”称为 Section，这也是洛谷 P1181 的经典问法。

输入输出格式在大多数 OJ 上是这样：

输入： 6 10 4 2 7 1 5 3 输出： 3

数据范围通常给到 N <= 100000，A_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)，条件是 j+1 到 i 这一段的和不超过 M。这个思路本身没有错，但时间复杂度是 O(N^2)，N=100000 时同样会超时，而且实现起来比贪心复杂太多。

这道题放在 C 语言入门阶段，真正的意图是让你发现一个规律：因为所有数都是正整数，从左往右扫描时，每一段总是“能不放就不切”才是最划算的。这个规律没有前缀和那么绕，也不需要动态规划，只要想明白一次，代码就非常简单。

1.3 一个反直觉的结论：不需要数组也能做对

这道题真正巧妙的地方在于：你根本不需要把整个数列全部读进数组。因为分段是从左往右连续切的，决定“下一段从哪里开始”的只有当前这一段的累加和，以及下一个数。只要维护两个变量——当前段的和 sum、已经封口的段数 cnt，就可以在输入的同一遍循环里把答案算出来。

我第一次意识到这点时，对“数据规模决定算法”有了非常直观的感受。用数组当然也没错，只是浪费内存，而且对初学阶段理解“在线处理”这个概念没有帮助。如果题目要求把所有数都存下来再做，N=100000 时开 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。

举个极端例子：M=5，数列是 3 2 4。用 > 判断，3+2=5 不封口，sum=5，下一次 5+4>5 封口，cnt=1，sum=4，最后 cnt+1=2，正确。用 >= 判断，3+2=5 立刻封口，cnt=1，sum=2，接着 2+4>5 又封口，cnt=2，最后输出 3，错。这个例子我每次讲都会让人自己跑一遍，因为很多人在笔试里不是不会贪心，而是败在这种边界条件的“手滑”上。

3. 可直接抄的 C 语言实现：变量、读入、输出

3.1 变量类型：为什么必须用 long long

这个题的数据范围在不同 OJ 上不完全一样，但常见的坑是 M 和 A_i 都可能很大。如果按习惯用 int 存 M 和 sum，sum 累加后一旦超过 2147483647 就会溢出变成负数，然后判断 sum + x > M 直接失效。所以我的建议是：M 和 sum 一律用 long long，x 也读成 long long，只有 n 和 cnt 用 int。

为什么 cnt 可以用 int？因为段数最多也就是 N 段，N 通常不超过 100000，int 足够。但和值不一样，段内累加可能超过 int 上限，这是很多人忽略的点。我见过太多人在这个题上吃 32 位整数的亏，所以宁可多写几个 long long，也不要在类型上抠门。

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、连续触发封口等情况：

用这些用例跑通过之后，再提交到 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 用 %d，sum 用 %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 往往能帮你提前发现类型不匹配的问题。数列分段只是入门题，但它把贪心、边界条件、数据类型、调试技巧全串在了一起，值得你认真对待一次。