Скачать программы Все программы автора
ЦЕПЬ
Есть N кусков цепи, каждый i-й из которых содержит Li звеньев. Можно разгибать произвольные звенья и потом сгибать их снова, соединяя отдельные куски.
Задание
Напишите программу CHAIN, которая по количеству кусков цепи N и количеству звеньев в кусках Li определяет минимальное количество звеньев, которые нужно разогнуть и согнуть снова, чтобы соединить все куски в одну цепь. Цепь не может иметь разветвлений, т.е. каждое звено должно быть соединено с двумя звеньями (кроме двух звеньев по краям цепи, которые должны быть соединены только с одним звеном).
Входные данные
В первой строке входного файла CHAIN.DAT находится целое число N (2£N£10 000). Во второй строке находятся N целых чисел Li (1£Li£1 000 000 000).
Выходные данные
В единственной строке выходного файла CHAIN.SOL должно находится целое число — наименьшее количество звеньев, которые необходимо разогнуть и согнуть снова, чтобы получить одну цепь из всех кусков.
Пример входных и выходных данных
CHAIN.DAT |
CHAIN.SOL |
3 100 3 4 |
2 |
{ Problem: CHAIN}
const
maxN=10000;
Inf=maxN-1;
type
list = array[1..maxN] of word;
procedure heapsort(var a: list; N: word);
var
i:word;
procedure Xch(i,j:word);
var
temp:word;
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
end;
procedure Heapify(what:word);
var
max:word;
begin
while what*2<=N do
begin
max:=what;
if a[what*2]>a[max] then
max:=what*2;
if (what*2+1<=N)AND
(a[what*2+1]>a[max]) then
max:=what*2+1;
if max=what then
what:=n
else
begin
Xch(what,max);
what:=max;
end;
end;
end;
begin
for i:=N div 2 downto 1 do
Heapify(i);
i:=N;
while N>1 do
begin
Xch(1,N);
Dec(N);
Heapify(1);
end;
N:=i;
end;
var
kuski:list;
s,N,M,i:word;
fi,fo:text;
temp:longint;
begin
assign(fi,'chain.dat');
assign(fo,'chain.sol');
reset(fi);
rewrite(fo);
readln(fi,N);
for i:=1 to N do
begin
read(fi,temp);
if temp>=Inf then
kuski[i]:=Inf
else
kuski[i]:=temp;
end;
heapsort(kuski,N);
s:=0;
i:=1;
M:=0;
while s+kuski[i]<N-i do
begin
Inc(M);
s:=s+kuski[i];
Inc(i);
end;
writeln(fo,N-M-1);
close(fi);
close(fo);
end.