原理

题目目标：将长度为 n 的数列分段，每段的和不超过 m，求最少分段数。
算法思想：贪心策略。遍历数组，尽可能将连续元素合并到当前分段，直到分段和超过 m 时结束当前分段，开启新分段。

步骤

1. ​输入处理：读取 n（数组长度）和 m（每段和上限），读取数组。
2. ​初始化变量：
   • ans：记录分段数。
   • k：当前处理到的数组索引（初始为 0）。
3. ​贪心分段：
   • 外层循环遍历数组，每次处理一个新分段。
   • 内层循环从 k 开始累加元素，直到分段和超过 m。
   • 当分段和超过 m 时，分段数 ans 加 1，并更新 k 到新分段的起点。
4. ​输出结果：最终分段数 ans。

图示法表示步骤（示例数组 [4, 2, 4, 5, 1]，m=6）

1. ​初始状态：k=0, ans=0
2. ​分段1：累加 4+2=6（未超 m），结束分段 → ans=1, k=2
3. ​分段2：累加 4 → 未超 m，结束分段 → ans=2, k=3
4. ​分段3：累加 5 → 未超 m，结束分段 → ans=3, k=4
5. ​分段4：累加 1 → 未超 m，结束分段 → ans=4, k=5
   最终结果：4 段。

代码关键行注释

int arrSep(vector<int> nums, int m) {  
    int ans = 0;  
    int k = 0;  
    while (k < nums.size()) {  
        int current_sum = 0;  
        int l = k;  // 当前分段的起点  
        // 内层循环累加元素，直到分段和超过 m  
        while (l < nums.size() && current_sum + nums[l] <= m) {  
            current_sum += nums[l];  
            l++;  
        }  
        ans++;  // 分段数加 1  
        k = l;  // 更新起点到下一分段的起始位置  
    }  
    return ans;  
}  

关键逻辑：

• 内层循环 while (l < nums.size() && current_sum + nums[l] <= m)：尽可能合并连续元素到当前分段。
• k = l：当前分段结束后，从新的位置 l 开始下一轮分段。

完整代码程序

#include <iostream>  
#include <vector>  
using namespace std;  

int arrSep(vector<int> nums, int m) {  
    int ans = 0;  
    int k = 0;  
    while (k < nums.size()) {  
        int current_sum = 0;  
        int l = k;  
        while (l < nums.size() && current_sum + nums[l] <= m) {  
            current_sum += nums[l];  
            l++;  
        }  
        ans++;  
        k = l;  
    }  
    return ans;  
}  

int main() {  
    int n, m;  
    cin >> n >> m;  
    vector<int> nums(n);  
    for (int i = 0; i < n; i++) {  
        cin >> nums[i];  
    }  
    int ans = arrSep(nums, m);  
    cout << ans << endl;  
    return 0;  
}  

时间复杂度

• ​时间复杂度：O(n)。外层循环遍历所有元素，内层循环每个元素最多被访问一次，总操作次数为 2n。
• ​空间复杂度：O(1)，仅用常数级变量。

总结

1. ​代码优点：
   • 贪心策略直观高效，时间复杂度为线性。
   • 变量命名清晰，逻辑简单。
2. ​潜在问题：
   • ​单个元素超过 m：若某个元素本身大于 m，内层循环会直接跳过，导致分段逻辑错误（如输入 [7], m=6，代码会进入死循环）。
   • ​函数参数传递：vector<int> nums 应改为引用传递（const vector<int>&）以避免拷贝开销。
3. ​改进建议：
   • 增加对单个元素超过 m 的特殊处理（题目隐含保证所有元素 ≤ m）。
   • 优化参数传递方式。