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.
Bạn đang xem bài 2: - DE THI HSG TIN 11 CO DAP AN