02/10/2018, 14:44
PTIT127C spoj ptit- Bố trí phòng họp
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT127C/ 1. Đề bài PTIT127C spoj Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần được bắt đầu ngay sau thời điểm s i và kết thúc tại thời điểm f i . Hỏi có thể bố trí phòng hội thảo ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT127C/
1. Đề bài PTIT127C spoj
Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần được bắt đầu ngay sau thời điểm sivà kết thúc tại thời điểm fi. Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp, sao cho khoảng thời gian làm việc của hai cuộc họp bất kỳ là không giao nhau.
Input
- Dòng đầu tiên chứa số nguyên dương n ( n <= 10000)
- Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương si, fi (si < fi <= 32000) ( 1 <= i <= n).
Output
- Dòng đầu tiên ghi số K là số các cuộc họp được chấp nhận phục vụ
2. Gợi ý PTIT127C spoj
– Các bạn dùng sắp xếp theo chiều tăng dần của B[i] (1<=i<=N) rồi dùng thuật toán tham lam tìm dãy cuộc hợp từ 1..i thỏa mãm B[i]>A[i]>=B[1..i-1].
3. Code tham khảo PTIT127C spoj Pascal
Code 1
const fi=';
nmax=10000;
type
data=longint;
dulieu=record
u,v:data;
end;
var
f:text;
A:array[1..nmax] of dulieu;
n:data;
procedure docfile;
var i:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
readln(f,a[i].u,a[i].v);
close(f);
end;
procedure sort(l,r: longint);
var
i,j,x: longint;
y:dulieu;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2].v;
repeat
while a[i].v<x do
inc(i);
while x<a[j].v do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
procedure xuli;
var i,j:data;
res,cuoi,k:data;
begin
res:=0; cuoi:=0;
i:=1;
while i<=n do
begin
if (a[i].u>=cuoi) and (a[i].v>cuoi) then
begin
inc(res);
cuoi:=a[i].v;
end;
inc(i);
end;
writeln(res);
end;
begin
docfile;
sort(1,n);
xuli;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | const fi='; nmax=10000; type data=longint; dulieu=record u,v:data; end; var f:text; A:array[1..nmax] of dulieu; n:data; procedure docfile; var i:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do readln(f,a[i].u,a[i].v); close(f); end; procedure sort(l,r: longint); var i,j,x: longint; y:dulieu; begin i:=l; j:=r; x:=a[(l+r) div 2].v; repeat while a[i].v<x do inc(i); while x<a[j].v do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; procedure xuli; var i,j:data; res,cuoi,k:data; begin res:=0; cuoi:=0; i:=1; while i<=n do begin if (a[i].u>=cuoi) and (a[i].v>cuoi) then begin inc(res); cuoi:=a[i].v; end; inc(i); end; writeln(res); end; begin docfile; sort(1,n); xuli; end. |
Code 2
Const Fi=';
Fo=';
Type Data = record
Site, Start, Finish: Longint;
End;
Var F: Text;
A: Array[1..10000] of Data;
N, I, J, Sum, Last: Longint;
Procedure Init;
Begin
Assign(f,fi);
Reset(f);
Readln(f,n);
For i:=1 to n do
Readln(f,a[i].Start,a[i].Finish);
close(f);
Sum:=0;
Last:=0;
i:=1;
End;
Procedure sort(l,r: longint);
var
i,j,x: longint;
y:data;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2].Finish;
repeat
while a[i].Finish<x do
inc(i);
while x<a[j].Finish do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
Procedure Process;
Begin
Sort(1,n);
While i<=n do
Begin
If (a[i].Start>=Last) and (a[i].Finish>last) then
Begin
Inc(Sum);
Last:=a[i].Finish;
Inc(k);
End;
Inc(i);
End;
End;
Procedure Print;
Begin
Assign(f,fo);
Rewrite(f);
Writeln(f,Sum);
Close(f);
End;
Begin
Init;
Process;
Print;
End.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | Const Fi='; Fo='; Type Data = record Site, Start, Finish: Longint; End; Var F: Text; A: Array[1..10000] of Data; N, I, J, Sum, Last: Longint; Procedure Init; Begin Assign(f,fi); Reset(f); Readln(f,n); For i:=1 to n do Readln(f,a[i].Start,a[i].Finish); close(f); Sum:=0; Last:=0; i:=1; End; Procedure sort(l,r: longint); var i,j,x: longint; y:data; begin i:=l; j:=r; x:=a[(l+r) div 2].Finish; repeat while a[i].Finish<x do inc(i); while x<a[j].Finish do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; Procedure Process; Begin Sort(1,n); While i<=n do Begin If (a[i].Start>=Last) and (a[i].Finish>last) then Begin Inc(Sum); Last:=a[i].Finish; Inc(k); End; Inc(i); End; End; Procedure Print; Begin Assign(f,fo); Rewrite(f); Writeln(f,Sum); Close(f); End; Begin Init; Process; Print; End. |
