专栏首页数据结构与算法P1181 数列分段Section I

P1181 数列分段Section I

题目描述

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

输入输出格式

输入格式:

输入文件divide_a.in的第1行包含两个正整数N,M,表示了数列A[i]的长度与每段和的最大值,第2行包含N个空格隔开的非负整数A[i],如题目所述。

输出格式:

输出文件divide_a.out仅包含一个正整数,输出最少划分的段数。

输入输出样例

输入样例#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]之和不超过109。

将数列如下划分:

[4][2 4][5 1]

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

暴力枚举只要不大于就不分!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=100001;
 6 int a[MAXN];
 7 int ans=0;
 8 int read(int &n)
 9 {
10     char ch=' ';int q=0,w=1;
11     for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
12     if(ch=='-')w=-1,ch=getchar();
13     for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;
14     n=q*w;    return n;
15 }
16 int main()
17 {
18     int n,m;
19     scanf("%d%d",&n,&m);
20     for(int i=1;i<=n;i++)
21         read(a[i]);
22     int now=0;
23     for(int i=1;i<=n;i++)
24     {
25         now=now+a[i];
26         if(now>m)
27         {
28             now=0;
29             ans++;
30             i--;
31         }
32         
33     }
34     printf("%d",ans+1);
35     return 0;
36 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P3391 文艺平衡树

    hh 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[...

    attack
  • BZOJ 1174: [Balkan2007]Toponyms

    Description 给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化. Input 第一行给出...

    attack
  • 洛谷P2234 [HNOI2002]营业额统计(01Tire树)

    题目描述 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本,账本上记录了...

    attack
  • P3391 文艺平衡树

    hh 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[...

    attack
  • BZOJ 1174: [Balkan2007]Toponyms

    Description 给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化. Input 第一行给出...

    attack
  • 冒泡排序简单操作模版及实例分析

    1 #include <bits/stdc++.h> 2 using namespace std; 3 inline int read() 4 { 5...

    Angel_Kitty
  • P3369 【模板】普通平衡树(Treap/SBT)

    题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询...

    attack
  • Splay详解(二)

    前言 在上一节中,我们讲述了Splay的核心操作rotate与splay 本节我会教大家如何用这两个函数实现各种强大的功能 为了方便讲解,我们拿这道题做例题...

    attack
  • Golang并发模型:一招教你无阻塞读写通道

    介绍Golang并发的模型写了几篇了,但一直没有以channel为主题进行介绍,今天就给大家聊一聊channel,channel的基本使用非常简单,想必大家都已...

    大彬
  • Golang并发模型:一招教你无阻塞读写通道

    介绍Golang并发的模型写了几篇了,但一直没有以channel为主题进行介绍,今天就给大家聊一聊channel,channel的基本使用非常简单,想必大家都已...

    大彬

扫码关注云+社区

领取腾讯云代金券