4

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

Вводные данные: дано целое число N — количество гвоздей (2 ≤ N ≤ 100). На другой строчке даны N чисел — координаты гвоздей (разные, неотрицательные числа, которые не превышают 10000).

Вывод: Вывести минимально возможную длину всех веревок.

Примеры Ввода/Вывода:

+------------------+-------------------+
| стандартный ввод | стандартный вывод |
+------------------+-------------------+
| 6                | 5                 |
| 3 4 12 6 14 13   |                   |
+------------------+-------------------+
| 7                | 5                 |
|  3 2 1 4 5 7 9   |                   |
+------------------+-------------------+

Мой код:

#include <iostream>
#include <conio.h>
#include <math.h>

using namespace std;

int n, sk[10000], min[10000], not[10000], tot;
int ats=0;

int main()
{

    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> sk[i];
    }
    for(int a=0;a<n;a++)
    {
        min[a]=11000;
    }
    for(int s=0;s<n;s++)
    {
        not[s]=0;
    }
    for(int y=0;y<n-1;y++)
    {
        if(not[y]==1){}
        else{
        for(int e=0;e<n;e++)
        {
            if(y==e){}
            else
            {
                if((abs(sk[y]-sk[e]))<min[y])
                {
                    min[y]=abs(sk[y]-sk[e]);
                    tot=e;
                }
                else if((abs(sk[y]-sk[e]))==min[y])
                {
                    if(not[tot]==1)
                    {

                    }
                    else
                    {
                        min[y]=abs(sk[y]-sk[e]);
                        tot=e;
                    }
                }
            }
        }
        for(int l=0;l<n;l++)
        {
            if(y==l){ }
            else if((abs(sk[y]-sk[l]))==min[y] && tot==l)
            {
                not[l]=1;
            }
        }
            //cout<<"dlia cifri: "<<sk[y]<<" mimimum "<<min[y]<<endl;
        }
    }
    for(int z=0;z<n;z++)
    {
        if(min[z]!=11000)
        {
        ats+=min[z];
        }
    }
    cout << ats << endl;
    return 0;
}
15
  • Ну то есть это одномерная задача. 24 мая 2018 в 1:05
  • Ээээ... Это как это для 3 4 12 6 14 13 получилось решение 5??? Какие пары гвоздей предлагается связывать, чтобы общая длина получилась 5? 24 мая 2018 в 1:12
  • @AnT пары: 3 и 4 (длина 1), 4 и 6 (длина 2), 12 и 13 (длина 1) и 13 и 14 (длина 1). Итого 1+2+1+1 = 5
    – rengetsu
    24 мая 2018 в 1:18
  • Да, верно... Не сообразил сразу. 24 мая 2018 в 1:22
  • @AnT сам уже неделю сижу
    – rengetsu
    24 мая 2018 в 1:23

3 ответа 3

4

Ясно, что соединять веревкой имеет смысл только соседние гвозди (после сортировки расположения гвоздей).

На самом деле - ну их нафиг, эти паросочетания (см. ниже). Прав @Igor - рекурсия (с мемоизацией) тут будет в самый раз.

Ясно, что первый и последний промежуток между гвоздями надо связывать обязательно. Если второй промежуток не связывать, то третий - надо связывать обязательно. Если второй промежуток связывать, то третий - нельзя связывать, а четвертый - надо связывать обязательно.

Получаем схему рекурсивного перебора:

связывать - не связывать - (рекурсивный вызов)
связывать - связывать - не связывать - (рекурсивный вызов)

(Опять же - это полностью соответствует ответу @Igor.)

На С++

#include <cassert>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iterator>

using Weight = unsigned;
using Weights = std::vector<Weight>;

Weight min_sum(const Weights &weights, size_t i = 0)
{
  assert(i < weights.size());
  size_t n = weights.size() - i;

  if (n == 1)
    return weights[i];
  else if (n == 2)
    return weights[i] + weights[i + 1];
  else if (n == 3)
    return weights[i] + weights[i + 2];
  else
    return std::min(
      weights[i] + min_sum(weights, i + 2), 
      weights[i] + weights[i + 1] + min_sum(weights, i + 3));  
}

int main()
{
  std::vector<int> nails;
  std::copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(nails));
  std::sort(nails.begin(), nails.end());
  std::copy(nails.begin(), nails.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  Weights weights;
  std::adjacent_difference(nails.begin(), nails.end(), std::back_inserter(weights));
  weights.erase(weights.begin());
  std::copy(weights.begin(), weights.end(), std::ostream_iterator<Weight>(std::cout, " "));
  std::cout << std::endl;

  std::cout << min_sum(weights) << std::endl;
}

http://coliru.stacked-crooked.com/a/13244f823d44f93d

Имеет смысл добавить мемоизацию по i, ибо возникновение одинаковых подзадач - возможно.


Непереборный подход:

Задача является задачей поиска реберного покрытия минимального веса в "зигзагообразном" двудольном графе (одна доля - четные гвозди, другая - нечетные, вес ребра W(u,v) равен расстоянию между гвоздями). Возможно (и даже скорее всего), это чересчур общий подход, т.е. "стрельба из пушки по воробъям", ибо граф имеет очень простую структуру, но пока закроем на это глаза.

Далее следуем предложенному самим Дэвидом Эппстейном вот здесь подходу. Ясно, что комбинации из трех последовательных ребер не имеют смысла - среднее ребро в такой комбинации является лишним. Тогда любое решение можно представить в виде некоего паросочетания M в исходном графе, плюс возможно несколько дополнительных ребер, предназначенных для присоединения непокрытых паросочетанием M вершин. Ясно, что непокрытые паросочетанием M вершины надо присоединять к M через ребра минимального веса, выходящие из таких вершин.

Пусть C(v) - это веc самого короткого ребра, выходящего из вершины v. Тогда вес решения, определяемого паросочетанием M, можно записать как

Σ C(v)    -    Σ С(u) + C(v) − W(u,v)
|              |
по всем v      по всем (u,v) из M

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

W'(u, v) = С(u) + C(v) − W(u,v)

Задача, возможно, упрощается "зигзагообразностью" двудольного графа. Задача, возможно, усложняется наличием отрицательных весов.

Осталось только решить задачу о паросочетании максимального веса в таком графе ))) (Хотя, как справедливо заметил в комментариях @Fat-Zer, задача интуитивно не выглядит более простой, чем исходная)


Например

1.

Гвозди       3   4   6   12   13   14
W              1   2   6    1    1
С(v)         1   1   2    1    1    1
W'             1   1  -3    1    1

Максимальное паросочетание M (одно из возможных): 3-4, 12-13 Добавляем непокрытые вершины ребрами минимальной длины:

3-4-6 12-13-14

Вес: 5

2.

Гвозди       1   2   3   4   5   7   9
W              1   1   1   1   2   2
С(v)         1   1   1   1   1   2   2
W'             1   1   1   1   1   2

Максимальное паросочетание M (одно из возможных): 2-3, 4-5, 7-9 Добавляем непокрытые вершины ребрами минимальной длины:

1-2-3 4-5 7-9

Вес: 5

3.

Гвозди       1   2   5   9   11   12
W              1   3   4   2    1
С(v)         1   1   3   2    1    1
W'             1   1   1   1    1

Максимальное паросочетание M: 1-2, 5-9, 11-12 Добавлять нечего.

Вес: 6

2
  • а новая задача не выродится ли в тот же самый перебор?
    – Fat-Zer
    24 мая 2018 в 4:50
  • @Fat-Zer: Не должна. Паросочетание максимального веса - классическая задача. Да и тут, по-моему, тривиальщина должна какая-то быть, из-за структуры графа... 24 мая 2018 в 4:51
3

Решение перебором:

рассмотрим два случая - 1. в начале находится один отрезок и пропуск, 2. в начале находятся два отрезка и пропуск. Потом для каждого из этих случаев рекурсивно рассматриваем оставшиеся гвозди.

Естественно, гвозди считаем упорядоченными на числовой прямой.

Равшан: "Писка: Фости, десять клох смен, ..."

3
  • 1
    Это полный перебор. 24 мая 2018 в 2:30
  • 1
    @AnT Спасибо. Это то, что я написал в первой строчке ответа.
    – user176262
    24 мая 2018 в 2:34
  • 2
    конечно хочется чего-то хитрожопого и динамического, но не думаю, что что-то умнее получится придумать....разве что отсечение заведомо худших вариантов не забыть добавить...
    – Fat-Zer
    24 мая 2018 в 2:40
1

Если я не ошибаюсь, и правильно все понял. То это задача на графах о поиске остова минимального веса графа. Решить можно либо алгоритмом Краскала либо алгоритмом Дейкстры.

Краскала (http://e-maxx.ru/algo/mst_kruskal_with_dsu)

Дейкстры (https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B)

Вот пример Краскала:

void kruskal()
{
    //  суммарный вес минимального остова
    int sum = 0;
    vector<pair<int, int>> mst;
    mst.clear();
    //  для корректной работы алгоритма все ребра графа должны быть отсортированы по весу
    sort(graph.begin(), graph.end());
    vector<int> tree_id(N);
    for (int i = 0; i < N; i++)
        tree_id[i] = i;
    //  обход списка ребер методом  раскала
    for (int i = 0; i < M; i++)
    {
        int a = graph[i].start, b = graph[i].fin, w = graph[i].weight;
        if (tree_id[a] != tree_id[b])
        {
            sum += w;
            mst.push_back(make_pair(a, b));
            int old_id = tree_id[b], new_id = tree_id[a];
            for (int j = 0; j < N; j++)
                if (tree_id[j] == old_id)
                    tree_id[j] = new_id;
        }
    }
    //  вывод минимального остова
    for (int i = 0; i < mst.size(); i++)
        printf("%d -> %d\n", mst[i].first, mst[i].second);
    printf("MST weight = %d\n", sum);
    mst.clear();
    tree_id.clear();
}
5
  • 1
    Остов (остовное дерево) всегда связно. Оптимальное решение данной задачи, очевидно, не всегда связно. 24 мая 2018 в 3:50
  • А это условие как понимать? "Надо соединить веревкой некоторые пары гвоздей так, чтобы к каждому гвоздю была привязана веревка" Если к каждому гвоздю привязана веревка, то как они могут быть не связаны?
    – ZeusBios
    24 мая 2018 в 3:52
  • 1
    "К каждому гвоздю была привязана веревка" не требует связности всей структуры. Например, если связать гвозди в пары, то "к каждому гвоздю будет привязана веревка". Но пары при этом все равно друг с другом никак связаны не будут. 24 мая 2018 в 3:53
  • Возможно вы правы. Но это не очевидно из условия. На мой взягляд это классическая постановка задачи о нахождении минимального остова
    – ZeusBios
    24 мая 2018 в 3:55
  • 2
    Минимальное остовное дерево в данном случае совершенно очевидно - это просто все гвозди связанные в одну линию. Все. И никакого алгоритма не надо. Поэтому как вы тут разглядели "классическую постановку задачи о нахождении минимального остова" мне не ясно. 24 мая 2018 в 4:09

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.