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 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

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.

P152PROB PTIT spoj – Phân nhóm