• 18 November 2013
    • Химия
    • Автор: Bern1

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


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

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


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


    Примеры:




    INPUT. IN


    OUTPUT. OUT




    5
    4
    10 0 12 2


    6




    • 18 November 2013
    • Ответ оставил: ПолинаАлексеевна

    //PascalABC.NET версия 3.2, сборка 1389
    //Если программа не запускается, то обновите версию
    begin
        var n := ReadInteger('n =');
        var a := ReadArrInteger('Массив', n);
        a.Sort;
    //    Println(a);
        
        var b := ArrFill(n + 1, 0);
        b[0] := 0;   
        b[1] := Maxint;   
        for var i := 2 to n do
            b[i] := min(b[i - 1], b[i - 2]) + abs(a[i - 1] - a[i - 2]);  
        
    //    Println(b);
        WriteLn(b[n]);
    end.

    Оцените ответ

    • НЕ НАШЛИ ОТВЕТ?
    Если вас не устраивает ответ или его нет, то попробуйте воспользоваться поиском на сайте и найти похожие ответы по предмету...

Последние и похожие вопросы