Подскажите алгоритм, как решить эту задачу??!
Подскажите алгоритм, как решить эту задачу??!Приближался Новый год и отец купил своим детям по подарку. Оказалось, что в них разное количество конфет. Тогда отец купил еще конфет и стал их раскладывать по подаркам следующим образом: брал подарок с наименьшим количеством конфет и добавлял в него одну конфету.
Требуется написать программу, которая найдет наименьшее количество конфет, оказавшихся в одном из подарков после завершения их раскладывания.
Входные данные
В первой строке N – количество детей и M – количество купленных конфет. Числа записаны через пробел, 1£N£10000, 1£M£1000000. Далее в N строках записаны числа в диапазоне от 1 до 30000 – количество конфет в подарках.
Выходные данные
Содержит одно найденное число.
Требуется написать программу, которая найдет наименьшее количество конфет, оказавшихся в одном из подарков после завершения их раскладывания.
Входные данные
В первой строке N – количество детей и M – количество купленных конфет. Числа записаны через пробел, 1£N£10000, 1£M£1000000. Далее в N строках записаны числа в диапазоне от 1 до 30000 – количество конфет в подарках.
Выходные данные
Содержит одно найденное число.
Гость
Ответ(ы) на вопрос:
ГостьA - массив кол-в отсортировали A minA = A[0] Цикл по A if( M > i*( A - minA) - M достаточно чтобы кол-во сравнялось во всех мешках [0,i] { M = M - i*(A - minA) minA = A } else - М не достаточно --> можно найти ответ { minA = minA + M/i break; } Чтобы не обрабатывать границы массива, лучше добавить элемент в массив A равный максимальному M. Тогда алгоритм всегда закончится внутри цикла
ГостьTurbo Pascal?
Не нашли ответ?
Похожие вопросы