P1181 数列分段Section I

admin

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 是最少划分的段数。

黄煦喆

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. }
    
23. 
    

复制代码

倚窗倾听风吹雨

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. }
    

复制代码

admin

很好的统计类程序题目，一个很直观的做法就是类似贪心，用一个和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则表示无法形成。注意注意！