洛谷 1181_数列分段_贪心

发布于 2019-05-03  889 次阅读


题目描述

给出一个数组,将这个数组分为若干个和不大于m的段,求最少分几个


思路

边读边做,贪心求解
O(n)


#include 
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int ans=0,t=0;
    for (int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if (t+x<=m) t+=x;
        else
        {
            t=x; 
            ans++;
        }
    }
    if (t>0) ans++;
    printf("%d\n",ans);
}
]]>