华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1309|回复: 3
打印 上一主题 下一主题

P1181 数列分段Section I

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-8-15 09:53:44 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
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 是最少划分的段数。

回复

使用道具 举报

9

主题

158

帖子

470

积分

华一学生

积分
470
QQ
沙发
发表于 2018-8-18 17:32:53 | 只看该作者
  1. #include<iostream>
  2. using namespace std;
  3. int i,k,t;
  4. long long s;
  5. int main()
  6. {
  7.     cin>>i>>k;
  8.     int a[i];
  9.     for(int j=0;j<i;j++)cin>>a[j];
  10.     for(int j=0;j<i;j++)
  11.     {
  12.         s+=a[j];
  13.         if(s>k)
  14.         {
  15.             s=0;
  16.             s+=a[j];
  17.             t++;
  18.         }
  19.     }
  20.     cout<<t+1;
  21.     return 0;
  22. }

复制代码
回复 支持 反对

使用道具 举报

50

主题

215

帖子

619

积分

高级会员

Rank: 4

积分
619
板凳
发表于 2018-8-20 10:34:50 | 只看该作者
  1. #include<iostream>
  2. using namespace std;
  3. int a[100010],m,n,ans,sum;
  4. int main()
  5. {
  6.     cin>>n>>m;
  7.     for(int i=1;i<=n;i++)
  8.         cin>>a[i];
  9.     for(int i=1;i<=n;i++)
  10.     {
  11.         sum+=a[i];
  12.         if(sum>m)
  13.         {
  14.             ans++;
  15.             sum=a[i];
  16.         }
  17.     }
  18.     ans++;
  19.     cout<<ans<<endl;
  20.     return 0;
  21. }
复制代码
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
地板
 楼主| 发表于 2019-8-9 15:55:06 | 只看该作者
很好的统计类程序题目,一个很直观的做法就是类似贪心,用一个和sum记录到当前为止的数字总和,若已经大于M则表示这个数不能装进去必须开一个新段,否则继续装,当然初始状态袋子数目cnt=1
  1. sum=0;cnt=1
  2.     for(int i=1;i<=n;i++)
  3.     {
  4.         sum+=a[i];
  5.         if(sum>m)
  6.         {
  7.             cnt++;
  8.             sum=a[i];
  9.         }
  10.     }
  11.    
复制代码

这里有一个隐患大家能想得到吗?假如M要是某个数字还要小怎么办呢?所以要加上特判。输入的时候要是某个ai大于M则表示无法形成。注意注意!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-25 14:41 , Processed in 0.191391 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表