Giá trị nhỏ nhất
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
Input:
stdin
Output:
stdout
Dạng bài
Bạn được cung cấp một mảng ~n~ số nguyên. Nhiệm vụ của bạn là tính giá trị nhỏ nhất của từng đoạn ~k~ phần tử, từ trái sang phải. (không hiểu thì xuống đọc giải thích ví dụ là hiểu)
Input
Dòng đầu tiên gồm 2 số nguyên ~n~ và ~k~ ~(k \le n)~ Dòng tiếp theo chứa n số nguyên dương ~a_1, a_2, …, a_n~ ~(a_i \le 10^6)~
Output
In ra ~n-k+1~ giá trị nhỏ nhất của ~n-k+1~ đoạn, cách nhau bởi dấu cách
Giới hạn
- Subtask 1: ~40~% số test có ~n \le 10^3~
- Subtask 2: ~30~% số test có ~n * k \le 10^7~
- Subtask 3: ~30~% số test có ~n \le 5 * 10^5~
Ví dụ
Sample input
5 3
2 1 5 3 4
Sample output
1 1 3
Giải thích ví dụ
- Giá trị nhỏ nhất của đoạn ~(2, 1, 5)~ là ~1~
- Giá trị nhỏ nhất của đoạn ~(1, 5, 3)~ là ~1~
- Giá trị nhỏ nhất của đoạn ~(5, 3, 4)~ là ~3~
Bình luận
Phù tìm hiểu mãi mới tối ưu hóa được tốc độ của code để dc 10/10 case chứ được 7/10 case hoài:)