Матч 389, Коробки с книгами (BoxesOfBooks)

Дивизион 2, Уровень 1

Имеется кипа книг, которую необходимо упаковать в коробки. Каждая коробка может содержать любое количество книг, но вес книг в ней не должен превышать maxWeight. Вы берете очередную коробку, кладете туда наибольшее допустимое по весу количество книг, потом ставите на нее печать, и берете следующую коробку. Каждая книга, которая кладется в коробку, берется только с верха кипы. Необходимо найти наименьшее количество коробок, в которое можно сложить все книги.

Класс: BoxesOfBooks

Метод: int boxes(vector<int> weights, int maxWeight)

Ограничения: 1 £ b £ 10000, 0 £ a £ b, 1 £ terms £ 20.

Вход. Массив весов книг weights и допустимый максимальный вес книг maxWeight в каждой коробке.

Выход. Наименьшее количество коробок, в которое можно сложить все книги.

Пример входа

weights	maxWeight
{5, 5, 5, 5, 5, 5}	10
{51, 51, 51, 51, 51}	100
{1, 1, 1, 7, 7, 7}	8
{}	7

Пример выхода

3

5

4

0

РЕШЕНИЕ

моделирование

Если массив пустой, возвращаем 0. Моделируем процесс перекладывания книг из кипы в коробки по описанному в условии алгоритму.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class BoxesOfBooks

{

public:

int boxes(vector<int> weights, int maxWeight)

{

int s, res, i;

if (weights.size() == 0) return 0;

for(s = res = i = 0; i < weights.size(); i++)

{

if (s + weights[i] > maxWeight) res++, s = 0;

s += weights[i];

}

return res + 1;

}

};