【題目描述】

對于給定的一個長度為N的正整數數列A[i]，現要將其分成連續的若干段，并且每段和不超過M（可以等于M），問最少能將其分成多少段使得滿足要求。

【輸入】

第1行包含兩個正整數N，M，表示了數列A[i]的長度與每段和的最大值；

第2行包含N個空格隔開的非負整數A[i]，如題目所述。

【輸出】

一個正整數，輸出最少劃分的段數。

【輸入樣例】

5 6?
4 2 4 5 1

【輸出樣例】

3

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; int a[N]; int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int sum=0;int res=1;for(int i=1;i<=n;i++){if(sum+a[i]>m){sum=a[i];res++;}elsesum+=a[i];}printf("%d\n",res);return 0; }

總結

以上是生活随笔為你收集整理的数列分段（信息学奥赛一本通-T1428）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。