数列分段

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 613 字

从左到右贪心装段，超上限就新开一段

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1428
// 题意：把长度为 N 的正整数数列切成若干连续段，要求每段和不超过 M，求最少能切成几段。
// 思路：从左到右贪心扫描，能装进当前段就装，装不下就新开一段。
// 复杂度：O(N) 时间 / O(1) 额外空间
// 易错点：段数从 1 起算（至少有一段），空数列不要输出 0。
// 易错点：每段和可以恰好等于 M，判断条件是「加上当前数后超过 M」才新开一段。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long m;
    if(!(cin >> n >> m)) return 0;
    int ans = 1;
    long long sum = 0;
    for(int i = 0; i < n; i++){
        long long x;
        cin >> x;
        if(sum + x > m){
            ans++;
            sum = x;
        }else{
            sum += x;
        }
    }
    cout << ans << "\n";
    return 0;
}

数列分段

正文

一本通·提高篇的其它内容