Информатика 7-8 класс Кресла
Одним зимним вечером компания из п друзей решила пойти в кинотеатр на премьеру нового фильма. Но когда они вошли в зал, то быстро заметили, что в зале находится ровно п кресел, а также рядом с каждым креслом указана его высота — щ. Кроме того, известно, что рост Ј-го человека равен bi. Проведя небольшой эксперимент, друзья заметили, что если человек садится на стул, то его неудобство будет равно модулю разницы между его ростом и высотой стула.
Так как среди этой компании нет участников муниципального этапа ВсОШ по информатике, они решили написать вам, чтобы вы помогли им сесть так, чтобы минимизировать суммарное неудобство всех друзей. Учтите, что каждый из компании должен занять какое-либо место, иначе все остальные не смогут спокойно смотреть кино.
Формат входных данных
Первая строка содержит одно натуральное число п (1 п 2 • 105 ) количество друзей.
Каждая из следующих п строк содержит одно целое число щ (1 щ 104 ) — высота Ј-го кресла.
Каждая из последующих п строк содержит одно целое число bi (1 bi 104 ) — рост Ј-го человека.
Формат выходных данных
В первой строке выведите одно число — минимальное суммарное неудобство.
Система оценки
Решения, корректно работающие при 1 п 8, будут получать не менее 20 баллов.
Решения, корректно работающие при равных между собой bi , будут получать не менее 10 баллов. Решения, корректно работающие при 1 щ, bi 2, будут получать не менее 30 баллов.
В случае, если ваше решение будет одновременно корректно работать при нескольких из этих условий, то оно будет получать не менее суммы указанных баллов.
Задача сводится к задаче о назначении, где нужно сопоставить людей и кресла таким образом, чтобы минимизировать суммарное неудобство. Простой перебор всех перестановок невозможен из-за большого количества вариантов (n!). Эффективный алгоритм для решения этой задачи — это алгоритм венгерского метода (или алгоритм Куна-Манкреса). Он находит оптимальное сопоставление за полиномиальное время (O(n³)).
Однако, поскольку ограничение по времени выполнения задачи не указано, и предполагается ограниченность ресурсов, можно предложить приближённый алгоритм, который будет работать достаточно быстро для умеренных значений n, но не гарантирует нахождение абсолютного минимума.
Приближенный алгоритм (Жадный алгоритм):
Этот алгоритм работает путем сопоставления каждого человека с ближайшим по росту креслом. Он не гарантирует оптимального решения, но даёт достаточно хорошее приближение.
Сортировка: Отсортировать высоты кресел h и роста людей b по возрастанию.
Сопоставление: Для каждого роста b[i] найти ближайшее кресло h[j], вычисляя |b[i] - h[j]| и выбирая минимальное значение. После того, как кресло выбрано, исключить его из рассмотрения.
Суммирование неудобств: Суммировать все модули разностей |b[i] - h[j]|
Код на Python (приближенный алгоритм):
n = int(input())
h = sorted([int(input()) for _ in range(n)])
b = sorted([int(input()) for _ in range(n)])
total_inconvenience = 0
used_chairs = [False] * n
for i in range(n):
min_inconvenience = float('inf')
best_chair = -1
for j in range(n):
if not used_chairs[j]:
inconvenience = abs(b[i] - h[j])
if inconvenience < min_inconvenience:
min_inconvenience = inconvenience
best_chair = j
total_inconvenience += min_inconvenience
used_chairs[best_chair] = True
print(total_inconvenience)
Этот код предоставит приблизительный ответ. Для больших значений n и для гарантии нахождения оптимального решения, следует реализовать венгерский метод, что потребует большего объема кода. Однако, для ограничений задачи, заданных в условии, этот приближенный жадный алгоритм может сработать достаточно эффективно.