洛谷P1181 数列分段Section I

￡神魔★判官ぃ 2022-05-31 11:19 134阅读 0赞

## 题目描述 ##

对于给定的一个长度为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是最少划分的段数。

题解：

用一个变量tmp进行累加，如果遇到tmp>M就ans++，同时tmp=0；

如果最后做完了tmp不是0，ans++

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    int number[100005];
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	int N, M;
    	cin >> N >> M;
    	int ans = 0;
    	int tmp = 0;
    	for (int i = 0; i < N; i++)
    	{
    		cin >> number[i];
    		if (tmp+number[i]>=M)
    		{
    			ans++;
    			if (tmp + number[i] == M)
    			{
    				tmp = 0;
    			}
    			else
    			{
    
    				if (number[i] <= M)
    					tmp = number[i];
    				else
    					tmp = 0;
    			}
    			//i--;
    		}
    		else
    		{
    			tmp += number[i];
    		}
    	}
    	if (tmp != 0) ans++;
    	cout << ans;
    	return 0; 
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，134人围观）

还没有评论，来说两句吧...

相关阅读

相关数列求和（洛谷P5745题题解，C++语言描述）

题目要求 [题目链接][Link 1] ![在这里插入图片描述][20210404021812720.png] 分析思路参考自[大佬的博客][Link 2]，

矫情吗；*/ 2022年10月22日 04:26/ 0 赞/ 166 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 273 阅读

相关洛谷P1181 数列分段Section I

题目描述对于给定的一个长度为N的正整数数列A\[i\]，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。输入输出格

￡神魔★判官ぃ/ 2022年05月31日 11:19/ 0 赞/ 135 阅读

相关洛谷P1042 乒乓球

题目背景国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择

朴灿烈づ我的快乐病毒、/ 2022年05月31日 08:39/ 0 赞/ 197 阅读

相关洛谷P1182 数列分段Section II

题目描述对于给定的一个长度为N的正整数数列A\[i\]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。关于最大值最小：例如一数列4 2 4

清疚/ 2022年05月29日 06:18/ 0 赞/ 207 阅读

相关洛谷P1372 又是毕业季I

题目背景 “叮铃铃铃”，随着高考最后一科结考铃声的敲响，三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍，憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑和泪水，全

迈不过友情╰/ 2022年05月26日 13:15/ 0 赞/ 116 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 271 阅读

相关洛谷P1540——机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

傷城~/ 2022年04月14日 06:55/ 0 赞/ 258 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 297 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 392 阅读