COMBINE (10Đ) CĨ N ĐOẠN DÂY XÍCH (N≤20000), MỖI ĐOẠN DÂY XÍCH LÀ MỘT...

BÀI 2: COMBINE (10đ) Cĩ n đoạn dây xích (N≤20000), mỗi đoạn dây xích là một chuỗi các mắt xích được nối với nhau.

Các đoạn dây xích này tách rời nhau. Mỗi đoạn xích cĩ khơng quá 20000 mắt xích

Bằng cách cắt ra một mắt xích, sau đĩ hàn lại, ta cĩ thể nối hai dây xích thành một đoạn. Thời gian để cắt và hàn mỗi mắt

xích là 1 đơn vị thời gian và được xem như bằng nhau với mọi mắt xích.

Yêu cầu: Hãy tính thời gian ngắn nhất để nối N đoạn dây xích thành 1 đoạn duy nhất.

Dữ liệu vào: COMBINE.INP

Dịng đầu ghi số N

Dịng thứ 2 ghi N số nguyên dương, mỗi số là độ dài của 1 đoạn xích.

Kết quả: COMBINE.OUT Một số duy nhất là thời gian ngắn nhất tìm được.

Time: 1s.

Ví dụ:

COMBINE.INP COMBINE.OUT

4

3

5 7 8 9

Chương trình:

begin

const fi='combine.inp';

assign(f,fo);

rewrite(f);

l:=d;r:=c;mid:=a[(d+c)div 2];

fo='combine.out';

tong:=0;

maxn=20001;

repeat

for i:=1 to n do

var f:text;

while a[l]<mid do inc(l);

begin

while a[r]>mid do dec(r);

i,n:word;

inc(tong,a[i]);

if l<=r then

tong:longint;

if tong>=n-i-1 then break;

a:array[0..maxn]of word;

end;

procedure input;

tam:=a[l];a[l]:=a[r];a[r]:=tam;

if tong=n-i-1 then write(f,tong)

inc(l);dec(r);

else write(f,n-i);

assign(f,fi);

close(f);

reset(f);

until l>r;

end;

readln(f,n);

if d<r then sort(d,r);

for i:=1 to n do read(f,a[i]);

if l<c then sort(l,c);

input;

sort(1,n);

procedure solve;

procedure sort(d,c:word);

solve;

var l,r,tam,mid:word;

end.