Bài toán nối xích

[dtpuyen1998]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Mặc dù biết là bài này xưa lắm rồi nhưng mà vẫn mong các anh chị hướng dẫn giùm
Người ta có N đoạn dây xích(N <= 20000), mỗi đoạn dây xích là 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 mắt 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 là bằng nhau với mọi mắt xích. Nhiêm vụ của bạn là phải nối chúng lại thành một đoạn dây xích duy nhất với thời gian ít nhất( hay số mắt xích bị cắt và hàn lại là ít nhất).

Input

Dữ liệu vào cho trong file văn bản có cấu trúc như sau: Dòng đầu tiên là số N, số đoạn xích. Những dòng tiếp theo ghi N số nguyên dương, số thứ i là số mắt xích có trong đoạn xích thứ i(i <= i <= N) Hai số cạnh nhau trên cùng một dòng cách nhau ít nhất một dấu cách.

Output

Một dòng duy nhất là số đơn vị thời gian mà bạn cần để nối N đoạn xích đã cho.

Example

Input:
3
2 3
4

Output:
2
Input
7
1 2 3 6 7 20 100
Output:
4

 

[harry9xsakura]

const fi='xich.inp';
fo='xich.out';
var n,kq:longint;
a:array[1..10000000]of longint;

procedure doc;
var i:longint;
begin
assign(input,fi);
reset(input);
readln(n);
for i:=1 to n do read(a);
close(input);
end;

procedure inkq;
var i:longint;
begin
assign(output,fo);
rewrite(output);
write(kq);
close(output);
end;

procedure qs(l,r:longint);
var key,i,j,tg:longint;
begin
if l>=r then exit;
i:=l;
j:=r;
key:=a[(l+r+1)div 2];
repeat
while a<key do inc(i);
while a[j]>key do dec(j);
if i<=j then
begin
tg:=a;
a:=a[j];
a[j]:=tg;
inc(i);
dec(j);
end;
until i>j;
qs(l,j);
qs(i,r);
end;

procedure xuli;
var i:longint;
begin
for i:=1 to n do
begin
if kq+a=n-i-1 then begin kq:=kq+a;exit;end;
if kq+a<n-i-1 then kq:=kq+a;
if kq+a>n-i-1 then begin kq:=kq+(a-(kq+a-n+i+1))+1; exit;end;
end;
end;

begin
doc;
qs(1,n);
xuli;
inkq;
end.

@};-
đề bài có vấn đề ạ cái này chỉ hiểu thôi chứ cũng không biết phải nói thế nào nứa
đại loại là sắp xếp (qs), sau đó mở lần lượt từ đầu đến cuối đến khi nào số xích được mở và hàn bằng số lượng các chuỗi còn lại -2