Thu nhỏ đống cỏ

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ đống cỏ xếp thành một hàng, đống thứ $i$ có chiều cao $h_{i}$ . Bạn có thể hoán đổi hai đống cỏ liền kề bất kỳ số lần, với điều kiện chênh lệch chiều cao của chúng không vượt quá $K$ .

Hãy tìm dãy chiều cao theo thứ tự nhỏ nhất theo thứ tự từ điển có thể đạt được.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$ .

$N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $h_{i}$ .

Dữ liệu ra

In ra $N$ dòng: chiều cao các đống cỏ sau khi sắp xếp theo thứ tự nhỏ nhất từ điển.

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq h_{i} \leq 10^{9}$
$1 \leq K \leq 10^{9}$

Subtask 1 (10%): $N \leq 100$

Subtask 2 (20%): $N \leq 5000$

Subtask 3 (70%): Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
5 3 7 7 3 6 2	6 7 7 2 3	Đống $h_{5} = 2$ muốn lên đầu nhưng bị chặn bởi $h_{4} = 6$ (chênh $4 > 3$ ). Đống $h_{3} = 3$ có thể vượt qua $h_{4} = 6$ (chênh $3 \leq 3$ ) nhưng bị chặn bởi $h_{1} = 7$ (chênh $4 > 3$ ). Đống $h_{4} = 6$ có thể vượt $h_{1} = 7$ (chênh $1 \leq 3$ ) và $h_{2} = 7$ (chênh $1 \leq 3$ ), lên vị trí đầu tiên. Kết quả tối ưu là $6, 7, 7, 2, 3$ .
4 2 3 1 4 2	1 2 3 4	Đống $h_{2} = 1$ vượt qua $h_{1} = 3$ (chênh $2 \leq 2$ ), lên đầu. Tiếp theo $h_{4} = 2$ vượt qua $h_{3} = 4$ (chênh $2 \leq 2$ ) rồi $h_{1} = 3$ (chênh $1 \leq 2$ ), lên đầu. Dãy kết quả là $1, 2, 3, 4$ .

Ghi chú

Dãy $A$ nhỏ hơn dãy $B$ theo thứ tự từ điển nếu tồn tại chỉ số $i$ đầu tiên mà $A_{i} < B_{i}$ .

Bình luận

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