題目鏈接
題目描述
對于給定的一個長度為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≤109，M大于所有數的最小值，Ai之和不超過10^9，
將數列如下劃分：
[4][24][51]
第一段和為4，第2段和為6，第3段和為6均滿足和不超過M=6，并可以證明3是最少劃分的段數，
思路：
貪心，對于當前元素只有并到其他段上和單獨一段兩種選擇，如果當前元素能找到和在一起的段就并上，找不到就自己一段，
代碼：
#include<iostream>
using namespace std;
int n, m, num[100010] = {0}, count = 1;
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> num[i];
int sum = num[0];
for(int i = 0; i < n; i++)
{
if(sum + num[i + 1] > m)
{
sum = 0;
count++;
}
sum += num[i + 1];
}
cout << count;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258421.html
標籤：其他
上一篇：寒假計劃