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

[Sibedir]

Рекурсия, короче.

Вот только до компа добрался (чтобы убедться в несостоятельности своих предидущих решений)))

[сфинкс]

возможная визуализация задачи

https://www.youtube.com/watch?v=cesSFpUl7uI

[Sibedir]

А вот уже без рекурсии

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

using namespace std;

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

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

    // Поиск минимальной длины связей
    // (в векторе connections длины отдельных связей меняются на минимальные длины связей от начала до текущего элемента)
    int MinL = connections[0];
    if (count > 1) {
        MinL = connections[0] + connections[1];
        connections[1] = MinL;
    }
    if (count > 2) {
        MinL = connections[0] + connections[2];
        connections[2] = MinL;
    }
    for (int i = 3 ; i < count; i++) {
        if (connections[i-1] < connections[i-2]) {
            MinL = connections[i] + connections[i-1];
        }
        else {
            MinL = connections[i] + connections[i-2];
        }
        connections[i] = MinL;
    }
    // (в итоге последняя ячейка вектора connections соответствует минимальной длине связей от начала до конца)
    
    // Вsвод результата
    cout << "Ответ:" << endl << MinL << endl;

    return 0;
}

[macomics]

Sibedir, но жадный алгоритм все же, по моему, короче

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

using namespace std;

// MAIN
int main()
{
    // Ввод данных
    int count;
    cin >> count;
    vector<int> coordinates;
    vector<int> connections;
    for (int i = 0; i < count ; ++i) {
        int buf;
        cin >> buf;
        coordinates.push_back(buf);
        connections.push_back(0);
    }
    int MinL = 0;
    for (int i = 0; i < count; ++i) {
        if (connections[i] != 0) continue;
        int k = -1;
        connections[i]++;
        for (int j = i + 1; j < count; ++j)
            if ((j != i) && (connections[j] == 0) && (k == -1 || abs(coordinates[i] - coordinates[k]) > abs(coordinates[i] - coordinates[j]))) k = j;
        for (int j = 0; j < count; ++j)
            if ((j != i) && (connections[j] != 0) && (k == -1 || abs(coordinates[i] - coordinates[k]) > abs(coordinates[i] - coordinates[j]))) k = j;
        connections[k]++;
        MinL += abs(coordinates[i] - coordinates[k]);
    }
    cout << "Ответ:" << endl << MinL << endl;

    return 0;
}

[Sibedir]

macomics, да, короче. Но считает не верно

6
1 2 4 7 9 10
Ответ:
6

https://onlinegdb.com/8QGxOCBc1Z

[Linok0036]

Sibedir, Спасибо большое! ❤️

[evg_m]

решил вернуться.
задача легче решается, если идти от обратного.

0. все столбы соединены.
1. мы не можем разорвать две крайние нити (нарушим связность).
среди прочих выбираем самую длинную. и разрываем.
2. получили ДВЕ полностью связанных меньшей длины (для каждой из них повторяем п.0, 1)