首页 > 其他 > 详细

洛谷-P1181 数列分段Section I

时间:2020-05-05 10:09:28      阅读:50      评论:0      收藏:0      [点我收藏+]

洛谷-P1181 数列分段Section I

原题链接:https://www.luogu.com.cn/problem/P1181


题目描述

对于给定的一个长度为N的正整数数列\(A_i\),现要将其分成连续的若干段,并且每段和不超过M(可以等于M),问最少能将其分成多少段使得满足要求。

输入格式

第1行包含两个正整数N,M,表示了数列\(A_i\)的长度与每段和的最大值,第2行包含N个空格隔开的非负整数\(A_i\),如题目所述。

输出格式

一个正整数,输出最少划分的段数。

输入输出样例

输入 #1

5 6
4 2 4 5 1

输出 #1

3

说明/提示

对于20%的数据,有N≤10;

对于40%的数据,有N≤1000;

对于100%的数据,有\(N≤100000,M≤10^9\),M大于所有数的最小值,\(A_i\)之和不超过\(10^9\)

将数列如下划分:

[4][24][51]

第一段和为4,第2段和为6,第3段和为6均满足和不超过M=6,并可以证明3是最少划分的段数。

C++代码

#include <iostream>
using namespace std;

int main() {
    int n,m,i,t=0,ans=1;
    cin>>n>>m;
    int a[n];
    for(i=0;i<n;++i)
        cin>>a[i];
    for(i=0;i<n;++i) {
        t+=a[i];
        if(t>m) {
            ++ans;
            t=a[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

洛谷-P1181 数列分段Section I

原文:https://www.cnblogs.com/yuzec/p/12829393.html

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