Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Đoạn gỗ

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Đoạn gỗ   Tue 27 Jul 2010, 13:24

Có n đoạn gỗ. Để xử lý chúng cần thời gian để chuẩn bị :

(a) Thời gian chuẩn bị cho đoạn gỗ đầu tiên là 1 phút.
(b) Sau khi xử lý xong đoạn gỗ có chiều dài l và trọng lượng w , không mất
thời gian xử lý nếu đoạn gỗ tiếp theo có độ dài l' và trọng lượng w' thỏa
l ≤ l' and w ≤ w'. Ngược lại mất 1 phút để chuẩn bị.


Tìm thời gian chuẩn bị ít nhất cho n đoạn gỗ. Ví dụ có 5 đoạn ( 9 , 4 ) ,
( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , và ( 4 , 1 ) , thì thời gian ít nhất là 2
vì có thể xử lý theo thứ tự như sau ( 4 , 1 ) ,
( 5 , 3 ) , ( 9 , 4 ) ,
( 1 , 2 ) , ( 2 , 5 ) .

Input

Dòng đầu là số lượng test, T. Mỗi test gồm 2 dòng : dòng đầu là số n , 1 <= n <= 5000 ,
và dòng thứ hai gồm 2n số nguyên dương l1 , w1 , l2 , w2 ,..., ln , wn ,
<= 10000 , li và wi là độ dài và trọng lượng của đoạn gỗ thứ i.

SAMPLE INPUT
3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1


Output



Ghi ra thời gian ít nhất trên từng dòng.
SAMPLE OUTPUT
2
1
3
Hướng dẫn: Bài này sử dụng tìm kiếm nhị phân!
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Đoạn gỗ   Wed 28 Jul 2010, 11:02

Làm giống bài đoạn nguyên thôi

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Đoạn gỗ   Wed 28 Jul 2010, 15:46

Bài đoạn nguyên mình đã làm và AC rồi.
Code:

Var            N,M:longint;
                A,B,F,L:Array[0..100001] of longint;

Procedure      Input;
Var            i:longint;
Begin
                Readln(N);
                For i:=1 to N do Readln(A[i],B[i]);
End;

Procedure      Init;
Begin
                A[0]:=Low(longint);
                A[N+1]:=High(longint);
                M:=1;
                L[N+1]:=1;
                F[1]:=N+1;
End;

Procedure      Sort(L,R:longint);
Var            i,j,Tam,Tam1,Key,Key1:longint;
Begin
                If L>=R then Exit;
                i:=L;
                j:=R;
                Key:=B[(L+R) div 2];
                Key1:=A[(L+R) div 2];
Repeat
                While (B[i]>Key) or ((B[i]=Key) and (A[i]<Key1)) do Inc(i);
                While (B[j]<Key) or ((B[j]=Key) and (A[j]>Key1)) do Dec(j);
                If i<=j then
                Begin
                        Tam:=B[i];
                        B[i]:=B[j];
                        B[j]:=Tam;
                        Tam1:=A[i];
                        A[i]:=A[j];
                        A[j]:=Tam1;
                        Inc(i);
                        Dec(j);
                End;
Until          i>j;
                Sort(L,j);
                Sort(i,R);
End;

Function        Find(i:longint):longint;
Var            Dau,Cuoi,Giua,j:longint;
Begin
                Dau:=1;
                Cuoi:=M+1;
Repeat
                Giua:=(Dau+Cuoi) div 2;
                j:=F[giua];
                If A[j]>=A[i] then      Dau:=Giua
                Else                    Cuoi:=Giua;
Until          Dau+1=Cuoi;
                Find:=F[Dau];
End;

Procedure      Xuli;
Var            i,j,k:longint;
Begin
                For i:=N downto 0 do
                Begin
                        j:=Find(i);
                        K:=L[j]+1;
                        If K>M then
                        Begin
                                M:=K;
                                F[K]:=i;
                        End
                        Else
                                If A[F[K]]<A[i] then F[K]:=i;
                        L[i]:=K;

                End;
End;

Procedure      Output;
Begin
                Writeln(M-2);
End;

BEGIN
                Input;
                Init;
                Sort(1,N);
                Xuli;
                Output;
END.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Đoạn gỗ   Wed 28 Jul 2010, 15:48

Còn bài trên thì thử các test thấy đúng nhưng nộp vẫn bị wa.
Code:

Const          MaxN=5001;
Var            T,h:longint;
                N,M:longint;
                A,B,F,L:Array[0..MaxN] of longint;

Procedure      Input;
Var            i:longint;
Begin
                Readln(N);
                For i:=1 to N do Read(A[i],B[i]);
End;

Procedure      Init;
Begin
                B[0]:=Low(longint);
                B[N+1]:=High(longint);
                M:=1;
                L[N+1]:=1;
                F[1]:=N+1;
End;

Procedure      Sort(L,R:longint);
Var            i,j,Key,Key1,Tam,Tam1:longint;
Begin
                If L>=R then Exit;
                i:=L;
                j:=R;
                Key:=A[(L+R) div 2];
                Key1:=B[(L+R) div 2];
Repeat
                While (A[i]>Key) or ((A[i]=Key) and (B[i]<Key1)) do Inc(i);
                While (A[j]<Key) or ((A[j]=Key) and (B[j]>Key1)) do Dec(j);
                If i<=j then
                Begin
                        Tam:=A[i];
                        A[i]:=A[j];
                        A[j]:=Tam;
                        Tam1:=B[i];
                        B[i]:=B[j];
                        B[j]:=Tam1;
                        Inc(i);
                        Dec(j);
                End;
Until          i>j;
                Sort(L,j);
                Sort(i,R);
End;

Function        Find(i:longint):longint;
Var            Dau,Cuoi,Giua,j:longint;
Begin
                Dau:=1;
                Cuoi:=M+1;
Repeat
                Giua:=(Dau+Cuoi) div 2;
                j:=F[giua];
                If B[j]>B[i] then      Dau:=Giua
                Else                    Cuoi:=Giua;
Until          Dau+1=Cuoi;
                Find:=F[Dau];
End;

Procedure      Xuli;
Var            i,j,k:longint;
Begin
                For i:=N downto 0 do
                Begin
                        j:=Find(i);
                        K:=L[j]+1;
                        If K>M then
                        Begin
                                M:=K;
                                F[K]:=i;
                        End
                        Else
                                If B[F[K]]<B[i] then F[K]:=i;
                        L[i]:=K;

                End;
End;

Procedure      Output;
Begin
                If h<T then    Writeln(M-2)
                Else            Write(M-2);
End;

BEGIN
                        Readln(T);
                        For h:=1 to T do
                        Begin
                                Input;
                                Init;
                                Sort(1,N);
                                Xuli;
                                Output;
                        End;
END.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Đoạn gỗ   Thu 29 Jul 2010, 18:09

Cái này còn tùy anh à. Một tỉ lệ nhỏ là đáp số bị sai. Nhưng nhỏ và rất rất nhỏ thôi. Như ở chỗ em nè, thầy ra đề, em làm đúng cuối cùng đáp số sai. laughing

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Đoạn gỗ   Thu 29 Jul 2010, 22:43

Anh chẳng thấy sai chỗ nào cả!

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Đoạn gỗ   Fri 30 Jul 2010, 11:55

Ko, ý em là đáp án của đề á.

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Đoạn gỗ   Today at 18:47

Về Đầu Trang Go down
 
Đoạn gỗ
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến