P152PROB PTIT spoj – Phân nhóm
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROB/ 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 ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROB/
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. |
