Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROB/
Nội dung bài viết
1. Đề bài P152PROB PTIT spoj
Pudge là một anh chàng rất thích hù dọa những người hay đi lẻ trong rừng. Một người được gọi là đi lẻ nếu như chênh lệch chiều cao với những người khác lớn hơn K. Một người được xếp chung nhóm với nhau nếu như trong nhóm đó, có một người khác có chênh lệch chiều cao với người đó không vượt quá K.
Ví dụ: với tập N = 5 người có các chiều cao: 6, 7, 3, 4, 9 và K = 1 thì ta sẽ có các mối quan hệ sau :
– người thứ 1 và 2 chung một nhóm (chiều cao 6, 7)
– 3 và 4 chung một nhóm (chiều cao 3, 4)
– 5 đi lẻ (chiều cao 9)
Vậy ta sẽ có 3 nhóm: {1, 2}, {3, 4} và {5}
Bạn hãy giúp Pudge tính xem có bao nhiêu nhóm trong rừng để anh còn biết mà hù dọa.
Input
– Dòng đầu chứa 2 số nguyên N, K (0 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^6).
– Dòng thứ hai trong chứa N số nguyên dương – chiều cao của mỗi người (giá trị không vượt quá 10^6).
Output
Dòng duy nhất chứa số nhóm trong rừng.
Example
Input:
7 1
2 6 1 7 3 4 9
Output:
3
Giải thích test;
Nhóm 1 những người có chiều cao: 2 1 3 4
Nhóm 2 gồm: 6 7
Nhóm 3 gồm: 9
2. Hướng dẫn P152PROB PTIT spoj
Thuật toán: Sắp xếp
Sắp xếp theo thứ tự tăng hoặc giảm dần chiều cao, rồi duyệt các phần tử a[i] và a[i + 1] nếu
thỏa mãn chênh lệch <= k thì chúng sẽ thuộc chung một nhóm.
Cấu trúc dữ liệu heap rất tiện lợi cho bài toán này.
3. Code tham khảo P152PROB PTIT spoj
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 | const fi=''; nmax=100000; type data=longint; var f:text; A:array[0..nmax+1] of data; n,k:data; procedure docfile; var i,x:data; begin assign(f,fi); reset(f); readln(f,n,k); for i:=1 to n do read(f,a[i]); close(f); end; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] 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,res,z:data; begin res:=0; i:=1; A[n+1]:=high(data); while i<=n do begin while abs(A[i]-a[i+1])<=K do inc(i); inc(res); inc(i); end; writeln(res); end; begin docfile; sort(1,n); xuli; end. |
Bài viết liên quan
- PTIT127C spoj ptit- Bố trí phòng họp
- P133SUMF spoj PTIT – cấp số cộng
- BCMARA spoj PTIT – Chạy đua marathon
- BCCOW spoj PTIT – Đi xem phim
- 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