| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P152PROB - ROUND 2B - Phân nhóm |
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
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-10 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2022-08-09 06:19:14
submit C++ thì WA, CPP14 thì lại AC :(( |
|
|
2021-06-20 15:20:03
CPP144 thì AC , C++ lại sai :VVVV, làm sub hơn cả chục lần :(( |
|
|
2017-08-20 19:41:15 Con Bò Huyền Thoại
http://kienthuc24h.com/p152prob-ptit-spoj-phan-nhom/ |
|
|
2017-04-23 11:55:36
ai cho mk xin bộ test với ạ, chẳng biết sai ở đâu T.T |
|
|
2016-02-13 16:48:06
Cẩn thận n = 0 nhé ! Sai hoài vì cái lỗi đó. |
|
|
2015-03-24 09:58:44 Con Bò Huyền Thoại
Last edit: 2017-08-20 19:41:20 |
