Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT127C/
Nội dung bài viết
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
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
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. |
Bài viết liên quan
- P133SUMF spoj PTIT – cấp số cộng
- BCMARA spoj PTIT – Chạy đua marathon
- BCCOW spoj PTIT – Đi xem phim
- P152PROB PTIT spoj – Phân nhóm
- P151PROG spoj PTIT – Xếp Hàng
- PTIT123A PTIT spoj – Sắp xếp 2
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương