Bút chì và hộp

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một dãy $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — độ đậm màu của $n$ chiếc bút chì. Bạn muốn xếp toàn bộ bút chì vào các hộp (số lượng hộp tùy ý, mỗi hộp có thể chứa số bút khác nhau) sao cho cả ba điều kiện sau đều được thỏa mãn:

Mỗi chiếc bút thuộc về đúng một hộp.
Mỗi hộp không rỗng phải chứa ít nhất $k$ chiếc bút.
Với mọi cặp bút $i, j$ thuộc cùng một hộp, $| a_{i} - a_{j} | \leq d$ .

Lưu ý chiều ngược lại không bắt buộc: hai chiếc bút có thể có $| a_{i} - a_{j} | \leq d$ nhưng vẫn được xếp vào hai hộp khác nhau.

Hãy xác định liệu có cách xếp hợp lệ hay không.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $k$ , $d$ — số lượng bút, kích thước tối thiểu của mỗi hộp không rỗng, và chênh lệch độ đậm tối đa cho phép trong cùng một hộp.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — độ đậm của từng chiếc bút.

Dữ liệu ra

In ra YES nếu tồn tại cách xếp hợp lệ, ngược lại in NO.

Ràng buộc

$1 \leq k \leq n \leq 5 \cdot 10^{5}$
$0 \leq d \leq 10^{9}$
$1 \leq a_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
6 3 10 7 2 7 7 4 2	YES	Có thể xếp tất cả $6$ bút vào cùng một hộp: chênh lệch lớn nhất là $7 - 2 = 5 \leq 10$ và kích thước $6 \geq 3$ .
6 2 3 4 5 3 13 4 10	YES	Xếp ${3, 4, 4, 5}$ thành hai hộp ${3, 4}$ và ${4, 5}$ (mỗi hộp $2$ bút, chênh lệch $\leq 1$ ), còn ${10, 13}$ vào hộp thứ ba (chênh lệch $3$ ).
3 2 5 10 16 22	NO	Với mảng sau khi sắp xếp $[10, 16, 22]$ : không cặp nào có chênh lệch $\leq 5$ , nên không thể ghép hai bút vào cùng hộp. Mà $n = 3$ và $k = 2$ buộc phải có ít nhất một hộp chứa $\geq 2$ bút.

Bình luận

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