当前位置：首页 > article >正文

计蒜客T1654 数列分段（C语言实现）

article 2024/9/20 13:51:23

【题目描述】对于给定的一个长度为n的正整数数列ai，现要将其分成连续的若干段，并且每段和不超过m（可以等于m），问最少能将其分成多少段使得满足要求。
【输入格式】第一行包含两个正整数n，m，表示了数列的长度与每段和的最大值。第二行包含n个空格隔开的非负整数ai。
【输出格式】一个正整数，输出最少划分的段数。
样例输入：
5 6
4 2 4 5 1
样例输出：
3
【C语言代码实现】

# include <stdio.h>
int main()
{
    int n, m;
    scanf("%d%d", &n, &m); // 输入两个正整数
    int a[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]); // 输入a数组元素
    }
    
    int dig = 0, s = 0; // 变量dig和s分别记录分段数量、当前数列的和
    for (int i = 0; i < n; ++i) {
        s += a[i]; // 累计数列的和
        if (s > m) { // 超过m表明产生一段
            ++dig; // 分段的数量加1
            s = 0; // 和归零
            --i; // 回退，要不然会少判断a[i]是否本身大于m
        } else if (i == n - 1) { // 不要忘记最后一个元素这里哦
            ++dig;
        } 
    }
    printf("%d", dig); // 输出
    return 0;
}