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


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

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


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


Примеры:




INPUT. IN


OUTPUT. OUT




5
4
10 0 12 2


6



1

Ответы и объяснения

2013-11-18T10:43:10+00:00
Function
min(a,b:integer):integer;
begin   if a<b then min := a   
else min := b;
end;  
procedure
Swap(var a,b:integer);
var   
q:integer;
begin   
q := a;   a := b;   b := q;
end;  
var   
n,i,j:integer;   
a,b:array[-1..100] of integer;
begin   
assign(input,'input.txt');
reset(input);   
assign(output,'output.txt');
rewrite(output);   
Read(n);   for i := 1 to n do Read(a[i]);   
for i := 1 to n do     
for j := i+1 to n do       
if a[i]>a[j] then Swap(a[i],a[j]);   
a[0] := Maxint;   
a[-1] := 0;   for i := 1 to n do     
b[i] := min(b[i-1],b[i-2])+abs(a[i]-a[i-1]);  
 WriteLn(b[n]);   close(input); close(output);
end.