首页 > 其他 > 详细

HDU 5783 Divide the Sequence (贪心)

时间:2016-08-03 09:00:01      阅读:341      评论:0      收藏:0      [点我收藏+]

把长度为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",n);
    }
    return 0;
}

 

HDU 5783 Divide the Sequence (贪心)

原文:http://www.cnblogs.com/yu0111/p/5731417.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!