После чудесного спасения из плена Бабы-яги, домовёнок Кузя оказывается в доме гимназистки Веры, которая в последнее время увлеклась живописью и рисованием. Чтобы помочь Вере в её…

Давайте подробно разберем задачу и подход к её решению.

Постановка задачи:

Есть n наборов карандашей, каждый набор — это один или несколько карандашей с целочисленной длиной. Нужно выбрать ровно k наборов так, чтобы разница между максимальной и минимальной длиной карандаша среди всех выбранных — была как можно меньше.

Обзор шагов решения:

1. Обработка входных данных:

   • Вводим n и k.
   • Для каждого набора считаем минимальную и максимальную длину карандашей внутри него.
   • В итоге мы получим для каждого набора два числа: минимальную и максимальную длину.

2. Преобразование данных:

   • Для каждого набора определяем минимальную длину (min_i) и максимальную длину (max_i).
   • Создаем массив пар (min_i, max_i).

3. Перебор вариантов:

   • Идея — упорядочить все наборы по их минимальной длине.
   • Тогда мы будем искать последовательность из k наборов подряд, для которых разница max_i - min_i минимальна.

4. Поиск минимальной разницы:

   • После сортировки по min_i перебираем все подряд идущие блоки длины k.
   • Для каждого блока определяем максимальную длину (max_in_block) и минимальную длину (min_in_block) в выбранных наборах.
   • Обновляем ответ, если разница max_in_block - min_in_block меньше текущего минимального.

Почему так?

• Отсортировать по min_i — помогает группировать наборы, которые имеют похожие минимальные значения карандашей.
• Выбор k последовательных наборов по отсортированному массиву минимальных значений — это эффективный способ проверить все возможные комбинации.

Реализация на Python:

n, k = map(int, input().split())

sets = []
for _ in range(n):
    data = list(map(int, input().split()))
    c = data[0]
    pencils = data[1:]
    min_length = min(pencils)
    max_length = max(pencils)
    sets.append((min_length, max_length))

# Сортируем по минимальной длине
sets.sort(key=lambda x: x[0])

# Инициализируем переменную для хранения наименьшей разницы
min_diff = float('inf')

# Перебираем все последовательности длины k
for i in range(n - k + 1):
    # Определяем максимальную и минимальную длину в выбранных наборах
    current_max = max(sets[j][1] for j in range(i, i + k))
    current_min = min(sets[j][0] for j in range(i, i + k))
    diff = current_max - current_min
    if diff < min_diff:
        min_diff = diff

print(min_diff)

Итог:

• Время выполнения — примерно O(n log n) из-за сортировки.
• Важный момент — аккуратно выбрать k последовательных наборов после сортировки, так как это гарантирует проверку всех вариантов, которые могут дать минимальную разницу.

Если есть дополнительные вопросы — спрашивайте!