Tin học Phân nhóm

[phkien@morsin.com]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Các bạn giúp mình bài này với:

Phân tích nhóm(phân nhóm, chia nhóm) là công việc phân chia cá phần tử trong một tập hợp thành một hay nhiều nhóm mà trong đó, các phần tử trong cùng một nhóm sẽ giống nhau hon so với phần tử thuộc nhóm khác.

Yêu cầu : Cho một tập hợp N số nguyên dương và một số nguyên dương K, nhiệm vụ của bạn là đếm xem có bao nhiêu nhóm. Biết rằng 2 phần tử được xếp chung với nhau nếu như chênh lệch giữa chúng không vượt quá K.

Giải thích : Với tập N = 7 số nguyên dương: 2, 6, 1, 7, 3, 4, 9 và K = 1 thì ta sẽ có các mối quan hệ sau:

• 2 và 1 chung một nhóm
• 2 và 3 chung một nhóm
• 6 và 7 chung một nhóm
• 3 và 4 chung một nhóm

Vậy ta sẽ có 3 nhóm : {1, 2, 3, 4}, {6, 7} và {9}

Dữ liệu vào: Từ file văn bản GROUP.INP

• Dòng đầu tiên chứa số nguyên T - là số bộ test cần kiểm tra ([tex]T\leq 20[/tex]).
• Các dòng tiếp theo chứa T bộ test, mỗi bộ test gồm 2 dòng :
  + Dòng đầu trong mỗi bộ test chứa 2 số nguyên dương N, K ([tex]1 \leq N\leq 10^{5}, 1\leq K\leq 10^{6}[/tex]) cách nhau ít nhât một dấu cách.
  + Dòng thứ hai trong mỗi bộ test chứa N số nguyên dương - là các phần tử trong tập hợp (giá trị không vượt quá [tex]10^{6}[/tex]).

Dữ liệu ra: Ghi ra file văn bản GROUP.OUT
Gồm T dòng, mỗi dòng chứa một số nguyên dương là số nhóm tương ứng của mỗi bộ test.

Ví dụ:

GROUP.INP​	GROUP.OUT
3 7 1 2 6 1 7 3 4 9 7 2 2 6 1 7 3 4 9 5 5 15 1 20 4 17	3 1 2

[TBODY] [/TBODY]

==================================================================================

Các bạn viết bằng ngôn ngữ Pascal hay c++ nhé! Tối ưu code để chạy càng nhanh càng tốt nhé! Thanks in advance!