Các đoạn nguyên

Tiêu đề: Các đoạn nguyên Tue 27 Jul 2010, 13:06

Littlelee có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Littlelee tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa.
Bạn là một lập trình viên!Bạn hãy giúp littlelee giải này!
Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.
Dữ liệu

Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.

Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.
Kết quả

Một số duy nhất là kết quả của bài toán.
Giới hạn

1 <= N <= 100000

1 <= A < B <= 1000000
Ví dụ

Dữ liệu

3

1 6

2 5

3 4
Kết quả

3

Dữ liệu

6

1 4

1 5

1 6

1 7

2 5

3 5
Kết quả

5

Tiêu đề: Re: Các đoạn nguyên Wed 28 Jul 2010, 08:29

Bài này là một bài cơ bản của QHD.

Xếp các đoạn theo thứ tự tăng dần của điểm đầu. QHD để tìm số đoạn bao hàm nhiều nhất.

Có điều nói vậy chứ Littlelee ko biết code đâu, mà dữ liệu lại lớn quá, hok làm tay được devilish

. Mấy bạn code để giúp Littlelee nhé

Tiêu đề: Re: Các đoạn nguyên Wed 28 Jul 2010, 16:20

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.

Tiêu đề: Re: Các đoạn nguyên Wed 28 Jul 2010, 20:58

Hovanthong cũng ở đà nẵng hay sao mà được làm admin
Hướng thì cũng giống ông lit mà cũng ko code được, đành copy code của chủ thớt về ngâm cứu
Crying or Very sad

Để ý thấy diễn đàn bây giờ là dành cho THPT rồi bounce

P/s ông lit kiếm đâu ra cái chữ kí đẹp thế bày tui làm với nào

Tiêu đề: Re: Các đoạn nguyên Wed 28 Jul 2010, 23:12

Thuật toán qua rõ ràng:
1.ta sort giảm B[i] nếu có b[i] bằng nhau thì sort tăng a[i].
2.Tìm dãy con tăng dài nhất bằng TKNP.
Mình không phải ở Đà Nẵng.

Tiêu đề: Re: Các đoạn nguyên Wed 28 Jul 2010, 23:13

Các bạn lên làm thành viên Forum mình nhé: [You must be registered and logged in to see this link.]

Tiêu đề: Re: Các đoạn nguyên Thu 29 Jul 2010, 18:16

Lên taochu.com mà tạo chữ kí lovestruck

Gà con Tổng số bài gửi : 17 Join date : 03/05/2010

thế hovanthong là thong93 ah.

» Đoạn gỗ
» Giải bài các số nguyên tố tương đương
» Số siêu nguyên tố
» Các số nguyên tố tương đương
» Vòng tròn nguyên tố