Pha Thuốc 3

Xem dạng PDF

Gửi bài giải

Điểm: 100,00
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Dạng bài

Per có ~n~ cây nấm, cây nấm thứ ~i~ có khối lượng ~A_i~.

Hôm nay cô ấy muốn pha thuốc. Cô ấy có thể dùng bao nhiêu cây nấm cũng được trong một lọ, nhưng hai cây nấm chênh lệch khối lượng quá ~k~ thì không được dùng trong cùng một lọ.

Hỏi số cây nấm nhiều nhất có thể dùng để pha hai lọ thuốc? (Per muốn thuốc của mình mạnh nhất có thể.)

Mỗi cây nấm chỉ được dùng cho nhiều nhất một lọ.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
  • Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~.

Kết quả

In ra số cây nấm nhiều nhất có thể dùng.

Ví dụ

Đầu vào:

6 3
1 2 5 7 9 10

Đầu ra:

5

Giải thích: Lọ thứ nhất dùng ~1, 2~ (chênh ~1~), lọ thứ hai dùng ~7, 9, 10~ (chênh ~3~). Tổng cộng ~5~ cây nấm. Không thể dùng cả ~6~ cây.

Giới hạn

  • ~1 \le n \le 10^5~
  • ~1 \le k, A_i \le 10^9~

Sau khi sắp xếp, mỗi lọ là một đoạn liên tiếp và hai đoạn phải rời nhau. Nếu chỉ pha được một lọ thì đáp án chính là số cây của lọ đó.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.