华师一附中OI组
标题:
P1181 数列分段Section I
[打印本页]
作者:
admin
时间:
2018-8-15 09:53
标题:
P1181 数列分段Section I
https://www.luogu.org/problemnew/show/P1181
题目描述
对于给定的一个长度为 N的正整数数列 Ai ，现要将其分成连续的若干段，并且每段和不超过 M （可以等于 M ），问最少能将其分成多少段使得满足要求。
输入输出格式
输入格式：
第1行包含两个正整数 N,M ，表示了数列Ai的长度与每段和的最大值，第 2 行包含 N 个空格隔开的非负整数 Ai ，如题目所述。
输出格式：
一个正整数，输出最少划分的段数。
输入输出样例
输入样例#1：
5 6
4 2 4 5 1
输出样例#1：
3
说明
对于 20% 的数据，有 N≤10；
对于 40% 的数据，有 N≤1000 ；
对于 100% 的数据，有 N≤100000,M≤10^9 ， M大于所有数的最小值，Ai 之和不超过 10^9 。
将数列如下划分：
[4][2 4][5 1]
第一段和为 4 ，第 2和为 6 ，第 3 段和为 6 均满足和不超过 M=6 ，并可以证明 3 是最少划分的段数。
作者:
黄煦喆
时间:
2018-8-18 17:32
#include<iostream>
using namespace std;
int i,k,t;
long long s;
int main()
{
cin>>i>>k;
int a[i];
for(int j=0;j<i;j++)cin>>a[j];
for(int j=0;j<i;j++)
{
s+=a[j];
if(s>k)
{
s=0;
s+=a[j];
t++;
}
}
cout<<t+1;
return 0;
}
复制代码
作者:
倚窗倾听风吹雨
时间:
2018-8-20 10:34
#include<iostream>
using namespace std;
int a[100010],m,n,ans,sum;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
sum+=a[i];
if(sum>m)
{
ans++;
sum=a[i];
}
}
ans++;
cout<<ans<<endl;
return 0;
}
复制代码
作者:
admin
时间:
2019-8-9 15:55
很好的统计类程序题目，一个很直观的做法就是类似贪心，用一个和sum记录到当前为止的数字总和，若已经大于M则表示这个数不能装进去必须开一个新段，否则继续装，当然初始状态袋子数目cnt=1
sum=0;cnt=1
for(int i=1;i<=n;i++)
{
sum+=a[i];
if(sum>m)
{
cnt++;
sum=a[i];
}
}
复制代码
这里有一个隐患大家能想得到吗？假如M要是某个数字还要小怎么办呢？所以要加上特判。输入的时候要是某个ai大于M则表示无法形成。注意注意！
欢迎光临 华师一附中OI组 (http://hsyit.cn/)
Powered by Discuz! X3.2