Задача
В. "Гвоздики"

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

Формат входного файла В первой строке входного файла INPUT.
IN записано число N – количество гвоздиков (2 ≤ N ≤ 100). В следующей строке
записано N чисел -координаты всех гвоздиков (неотрицательные целые числа,не
превосходящие 10000).

Формат выходного файла
В выходной файл OUTPUT. OUT нужно вывести единственное
число -минимальную суммарную длину всех ниточек.

Примеры:




INPUT. IN


OUTPUT. OUT




5
4
10 0 12 2


6

Эта задача — классическая задача на минимальное остовное дерево, но в упрощённой версии, так как гвоздики расположены на одной прямой. Задача сводится к соединению соседних гвоздиков, что минимизирует суммарную длину всех ниточек.

Подход к решению

1. Сортировка координат гвоздиков: Поскольку гвоздики лежат на одной прямой, оптимальное решение заключается в соединении каждого гвоздика с ближайшим. Поэтому сначала нужно отсортировать координаты гвоздиков в порядке возрастания. Это позволяет нам рассматривать их как точки на числовой оси в порядке расположения.

2. Вычисление расстояний между соседними гвоздиками: После сортировки для минимальной суммарной длины достаточно соединить каждый гвоздик с ближайшим, то есть рассчитывать расстояние между каждой парой соседних гвоздиков.

3. Суммирование расстояний: Для получения минимальной суммарной длины всех ниточек нужно сложить все рассчитанные расстояния между соседними гвоздиками.

Алгоритм

Пусть N — количество гвоздиков, а массив coordinates содержит их координаты:

1. Прочитать N и coordinates.
2. Отсортировать массив coordinates в порядке возрастания.
3. Вычислить расстояния между соседними гвоздиками и сложить их: $$\text{total\_length} = \sum_{i=1}^{N-1} (\text{coordinates}[i] - \text{coordinates}[i-1])$$

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

python
def minimal_length(n, coordinates):
    # Шаг 1: Сортировка координат
    coordinates.sort()
    
    # Шаг 2: Нахождение суммарной длины ниточек
    total_length = 0
    for i in range(1, n):
        total_length += coordinates[i] - coordinates[i - 1]
    
    return total_length

Пример

Рассмотрим пример из условия:

• Входные данные: N = 5, координаты [4, 10, 0, 12, 2]
• Шаг 1: Сортируем координаты: [0, 2, 4, 10, 12]
• Шаг 2: Вычисляем расстояния между соседями:
  • Между 0 и 2: $2 - 0 = 2$
  • Между 2 и 4: $4 - 2 = 2$
  • Между 4 и 10: $10 - 4 = 6$
  • Между 10 и 12: $12 - 10 = 2$
• Сумма расстояний: $2 + 2 + 6 + 2 = 12$

Ответ: 12.

Таким образом, минимальная суммарная длина всех ниточек составляет 12.

Вывод

Это решение оптимально по времени и пространству, так как сортировка массива занимает $O(N \log N)$, а сумма расстояний требует $O(N)$.