Матч 430, Создание групп (CreateGroups)

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

Элемент массива groups[i] содержит количество студентов, обучающихся в институте по i - ому расписанию. Число студентов, обучающихся по каждому из расписаний, должно варьироваться от minSize до maxSize. Однако изначально студенты записывались на обучение по своему желанию, не соблюдая это правило. Найти наименьшее количество студентов, которое необходимо перевести с обучения по одному расписанию на другое, чтобы выполнялось упомянутое условие. Вернуть -1, если этого совершить нельзя.

Класс: CreateGroups

Метод: int minChanges(vector<int> groups, int minSize,

int maxSize)

Ограничения: groups содержит от 1 до 50 элементов, 1 £ maxSize, groups[i] £ 10⁶, 1 £ minSize £ maxSize.

Вход. Массив groups и два целых числа minSize и maxSize.

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

Пример входа

groups	minSize	maxSize
{10, 20}	10	15
{20,8,6}	10	15
{50,10,20,20,5}	15	30

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

5

6

20

РЕШЕНИЕ

элементарные вычисления

В переменной s найдем общее число студентов. Согласно правилу, в институте может обучаться не более maxSize * n и не менее minSize * n студентов, где n – количество расписаний. Вычислим количество студентов upper, которые составляют излишек в группах и которых обязательно надо переводить, а также число студентов lower, которыми обязательно следует заполнить группы. Ответом задачи будет значение max(lower, upper).

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <numeric>

using namespace std;

class CreateGroups

{

public:

int minChanges(vector<int> groups, int minSize, int maxSize)

{

int n = groups.size(), i, lower = 0, upper = 0;

int s = accumulate(groups.begin(),groups.end(),0);

if ((s > maxSize * n) || (s < minSize * n)) return -1;

for(i = 0; i < groups.size(); i++)

{

if (groups[i] < minSize) lower = lower + minSize - groups[i];

if (groups[i] > maxSize) upper = upper + groups[i] - maxSize;

}

return max(lower,upper);

}

};