УМОЛЯЮ СДАЮ ЧЕРЕЗ ЧАС B. Справедливое распределение подарков
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Дед Мороз подарил семиклассникам на новогоднем вечере большой мешок подарков. В классе учатся n детей. Когда открыли мешок, оказалось, что в нем находятся n+1 наборов конфет в различных красивых упаковках. Увидев, что на дне каждой упаковки указано количество конфет в наборе, дети выяснили, что в i-ом наборе находится ai конфет.

Дед Мороз попросил детей распределить наборы между собой одним из двух :

Один из детей получает два набора, остальные n−1 детей — по одному набору.
Все n детей получают по одному набору, оставшийся набор возвращается Деду Морозу.
Дети хотят распределить между собой эти наборы наиболее справедливым образом, считая несправедливостью распределения разность между максимальным количеством конфет, доставшихся одному ребенку и минимальным количеством конфет, доставшихся одному ребенку.

детям распределить подарки одним из Деда Мороза так, чтобы несправедливость распределения была наименьшей.

Входные данные
В первой строке дано одно целое число n (2≤n≤3000) — количество детей.

Вторая строка содержит n+1 целых чисел a1,a2,…,an+1 (1≤ai≤1000).

Выходные данные
Выведите единственное число — несправедливость наиболее справедливого распределения подарков.

Система оценки
Подзадача 1. Дополнительные ограничения: n=2. Оценивается в

Подзадача 2. Дополнительные ограничения: n=3. Оценивается в

Подзадача 3. Дополнительных ограничений нет. Оценивается в

Все подзадачи независимы. за каждый тест начисляются независимо.

Примеры
входные данныеСкопировать
2
6 3 4
выходные данныеСкопировать
1
входные данныеСкопировать
3
10 13 20 20
выходные данныеСкопировать
3
входные данныеСкопировать
4
23 42 35 52 100
выходные данныеСкопировать
29

Добрый день, ученик!

Для начала разберем, что требуется сделать в этой задаче. У нас есть мешок с подарками, в котором находятся n+1 наборов конфет. Каждый набор содержит определенное количество конфет, которое указано на дне упаковки. Наша задача - распределить наборы между детьми таким образом, чтобы несправедливость распределения (разность между максимальным и минимальным количеством конфет, доставшихся ребенку) была минимальной.

Для решения этой задачи можно использовать следующий алгоритм:
1. Сначала отсортируем наборы конфет по количеству конфет в порядке возрастания.
2. Распределим наборы между детьми следующим образом:
- Если n равно 2 (подзадача 1), первый ребенок получает максимальный набор, а второй ребенок получает оставшийся набор. Это будет самым справедливым распределением, так как только двое детей.
- Если n равно 3 (подзадача 2), первый ребенок получает первый набор, второй ребенок получает второй набор, а третий ребенок получает оставшийся набор. Опять же, это будет самым справедливым распределением, так как только трое детей.
- Если n больше 3 (подзадача 3), первый ребенок получает первый и последний наборы (с наибольшим и наименьшим количеством конфет соответственно), а остальные n-1 детей получают по одному набору из оставшихся.
3. После распределения подсчитаем разность между максимальным и минимальным количеством конфет, доставшихся ребенку. Это и будет несправедливостью наиболее справедливого распределения подарков.

Посмотрим на примеры из задачи, чтобы лучше понять, как работает алгоритм.

Пример 1:
Входные данные:
2
6 3 4
В данном случае у нас двое детей, поэтому это подзадача 1. Отсортируем наборы по количеству конфет: 3, 4, 6. Распределим их между детьми: первый ребенок получает наборы с 3 и 6 конфетами, а второй ребенок получает оставшийся набор с 4 конфетами. Разность между максимальным и минимальным количеством конфет будет 6 - 3 = 3. Ответ: 3.

Пример 2:
Входные данные:
3
10 13 20 20
В данном случае у нас трое детей, поэтому это подзадача 2. Отсортируем наборы по количеству конфет: 10, 13, 20, 20. Распределим их между детьми: первый ребенок получает набор с 10 конфетами, второй ребенок получает набор с 13 конфетами, а третий ребенок получает оставшийся набор с 20 конфетами. Разность между максимальным и минимальным количеством конфет будет 20 - 10 = 10. Ответ: 10.

Пример 3:
Входные данные:
4
23 42 35 52 100
В данном случае у нас больше трех детей, поэтому это подзадача 3. Отсортируем наборы по количеству конфет: 23, 35, 42, 52, 100. Распределим их между детьми: первый ребенок получает наборы с 23 и 100 конфетами, а остальные три ребенка получают по одному набору соответственно с 35, 42 и 52 конфетами. Разность между максимальным и минимальным количеством конфет будет 100 - 23 = 77. Ответ: 77.

Таким образом, мы нашли ответ для каждого из примеров. Если у тебя возникли вопросы или нужно что-то пояснить, пожалуйста, обращайся!