Выведите минимально возможную общую длину всех нитей

[Linok0036]

Помогите пожалуйста написать код на с++: У нас есть таблица, на которой по одной прямой расположены гвозди. Любые два гвоздя мы можем соединить нитью. Необходимо связать некоторые пары гвоздей нитями так, чтобы к каждому гвоздю была привязана хотя бы одна нить, и общая длина нитей была минимальной.
Ввод: В первой строке дано натуральное число n (2 <= n <= 100). Во второй строке находятся n различных целых чисел a[i] (0 <= a[i] <= 10000), которые указывают координаты гвоздей на прямой.
Вывод: Выведите минимально возможную общую длину всех нитей.

Например:
7
3 2 1 4 5 7 9
Ответ:
5

Или
6
1 2 4 7 9 10
Ответ:
5

[evg_m]

жадный алгоритм. каждый раз соединяем два гвоздя между которыми самое короткое расстояние.

[Sibedir]

А задание всё? Просто, если гвозди на одной прямой, то
минимальная длина нити = максимальная координата - минимальная координата.
Т.е. есть самый правый и самый левый гвозди. Последовательно связав каждые соседние гвозди, мы получим цепочку от крайнего к крайнему без наложений - это и есть минимальная длина нити.

[Sibedir]

гвозди нити.png

[macomics]

Вот только это не сходится с ответом в первом примере

А вот на второй картинке правильный ответ. Длина нити как раз 5 - жадный алгоритм

[macomics]

Вернее жадный алгоритм создаст вот такие связи

[Sibedir]

macomics, а, ну да, туплю. Тогда так
0. L = 0
1. Отсортировать и поместить в односвязный список
2. Если n > 5 то п.3 иначе п.6
3. L = L + [1]-[0] + [n-1]-[n-2]
4. Удалить [1], [2], [n-1] и [n-2]. n = n-4
5. Переход на п. 2
6. Разобрать оставшиеся варианты для n = 2, 3, 4 или 5

- добавлено
Неее! Фигня. Не правильно

[macomics]

Тут скорее нужен массив с флагами привязки
1) Ввели данные о позиции гвоздей в массив
2) Создали массив привязок заполненный FALSE
3) Проходим по массиву позиций пропуская элементы, у которых в массиве привязок TRUE
3.1) Запомнили индекс привязки равный -1 (флаг не найден)
3.2) Проходим по всему массиву позиций
3.2.1) Если индекс равен -1 или длина от текущего элемента до элемента выбранного внешним циклом меньше чем до элемента с индексом, тогда запоминаем новый индекс элемента
3.3) Помечаем в массиве привязок индекс цикла и выбранный индекс как TRUE
3.4) Добавляем длину веревки

[Sibedir]

Аааа, во как
Связать все гвозди по порядку и, пока можно убрать какую-нибудь связь, убираем самую длинную. Проверка на возможность разрыва связи состоит в том, что связь можно убрать, если она между гвоздями, которые оба есть в других связях.

[Sibedir]

Linok0036,

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Функция поиска минимальной длины связей для заданного участка
int MinL (const vector<int>& connections,
                       int   begin      ,
                       int   count      ) {
    if      (count == 1) {
        return connections[begin];
    }
    else if (count == 2) {
        return connections[begin] + connections[begin+1];
    }
    else if (count == 3) {
        return connections[begin] + connections[begin+2];
    }
    else {
        int L1 = connections[begin] + MinL (connections, begin+1, count-1);
        int L2 = connections[begin] + MinL (connections, begin+2, count-2);
        if (L1 < L2) return L1;
        else         return L2;
    }
}

// MAIN
int main()
{
    // Ввод данных
    int n;
    cin >> n;
    vector<int> coordinates;
    for (int i = 0; i < n ; i++){
        int buf;
        cin >> buf;
        coordinates.push_back(buf);
    }
    sort(coordinates.begin(), coordinates.end());

    // Формирование списка связей
    vector<int> connections;
    for (int i = 0; i < n-1 ; ++i){
        int L = coordinates[i+1] - coordinates[i];
        connections.push_back(L);
    }

    int L = MinL (connections, 0, n-1);

    // Вsвод результата
    cout << "Ответ:" << endl << L << endl;

    return 0;
}