洛谷P1181 数列分段Section I

￡神魔★判官ぃ 2022-05-31 11:19 179阅读 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 条评论，179人围观）

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

相关阅读

相关洛谷——P1838 三子棋I

P1838 三子棋I 题目描述小a和uim喜欢互相切磋三子棋。三子棋大家都玩过是吗？就是在九宫格里面OOXX（别想歪了），谁连成3个就赢了。由于小a比较愚蠢，

青旅半醒/ 2023年10月02日 12:06/ 0 赞/ 12 阅读

相关 Java实现洛谷 P1062 数列

P1062 数列 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ib

冷不防/ 2023年07月19日 10:32/ 0 赞/ 24 阅读

相关【洛谷P1939】矩阵加速（数列）

Description 定义序列a的通项公式为$a\_i=\\left\\\{\\begin\{aligned\}1 && i \\leq 3 \\\\a\_\{i-1\

刺骨的言语ヽ痛彻心扉/ 2023年06月05日 08:52/ 0 赞/ 15 阅读

相关【洛谷P1962】斐波那契数列

Description 给定n，求斐波那契数列第n项对1e9+7取模的值 Solution 由于数据太大，朴素的递推会超时，所以我们考虑用矩阵优化。首先我们要

梦里梦外;/ 2023年06月05日 08:52/ 0 赞/ 26 阅读

相关 P1182 数列分段 Section II（尚有疑问）

[题解来自这里][Link 1] [题目][Link 2] 问题是：我怎么知道mid该如何确定? version 1.0 `int mid =( sum[1]+su

青旅半醒/ 2022年11月13日 12:25/ 0 赞/ 7 阅读

相关洛谷p1164

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

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

相关洛谷P1181 数列分段Section I

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

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

相关洛谷P1182 数列分段Section II

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

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

相关洛谷 P3382

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

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

相关洛谷 P4961

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

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