526互联

数列分段 Section I

发布时间 2023-06-17 09:08:10作者: Momo·Trace

数列分段 Section I

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #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][2 4][5 1]\)

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

解析

贪心

步骤：

  1. 每次判断\(sum+\)当前数列长度 是否 \(<m\)，如果\(<\)则\(sum+\)当前数。\(sum\)代表的就是当前段的总长度，这段话则表示当前段还能容纳下这段数列。

  2. 如果\(\geq m\)，则需要成立一个新的段。则\(ans++\)，\(ans\)表示总段数。如果正好\(sum=m\)，则代表上一段没有剩余，如果有剩余的话，就不能将这段数列包含进去，所以\(sum=a_i\)，就将这段数列作为新段的开头。

  3. 最后如果\(sum>0\)，则代表还有数没有被分段，所以\(ans++\)。输出\(ans\)。

代码

#include <bits/stdc++.h>
using namespace std;  
int a[100010],ans,sum;  //定义变量
int main()
{
	int n,m;
	cin >> n >> m;   
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];       //输入
	}
	for(int i=1;i<=n;i++)
	{
		if(sum+a[i]<m) 
		{
			sum+=a[i]; //判断是否可以入段
		}
		else{
			ans++; //不可入段则总段数++
			if(sum+a[i]>m)
			{
				sum=a[i]; //判断有剩余的情况，如果有就不能将这段数列包含进去，就将这段数列作为新段的开头。
			}
			else{ 
				sum=0; //没有剩余则段的长度归0
			}
		}
	}
	if(sum>0)
	{//判断一个数还没有被分段的特殊情况
		ans++;
	}
	cout << ans; //输出总段数
	return 0;  
}