HDU 5783 Divide the Sequence (贪心)

把长度为n的序列分成尽量多的连续段，使得每一段的每个前缀和都不小于0。保证有解。

从后往前贪心分段即可。大于等于0的为一段，遇到负数就一直相加到非负为止！（注意精度问题 用long long）

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N=1000010;
LL a[N];
int main()
{
    LL n,i;
    while(~scanf("%lld",&n)) {
        for(i=1; i<=n; i++)
            scanf("%lld",&a[i]);
        LL sum=0;
        for(i=n; i>=1; i--) {
            sum+=a[i];
            if(sum>=0)
                sum=0;
            else
                n--;
        }
        printf("%lld
",n);
    }
    return 0;
}