#1587. Tìm Min đoạn tịnh tiến (MINK)

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho mảng số nguyên A gồm n phần tử và số nguyên k . Hãy tìm giá trị nhỏ nhất của từng đoạn con liên tiếp có độ dài k . Cụ thể, cần tìm \min(A[i], A[i+1], \dots, A[i+k-1]) với mọi 1 \le i \le n-k+1 .

Dữ liệu:

  • Dòng đầu chứa hai số nguyên n, k ( 1 \le k \le n \le 10^6 ).
  • Dòng thứ hai chứa n số nguyên A_1, A_2, \dots, A_n ( |A_i| \le 10^9 ).

Kết quả:

  • In ra trên một dòng các giá trị nhỏ nhất tìm được theo thứ tự các cửa sổ trượt.

Ví dụ:

Dữ liệu:

10 3
2 5 3 7 1 4 2 6 9 8

Kết quả:

2 3 1 1 1 2 2 6 

Giải thích:

  • Cửa sổ [2, 5, 3] \to min = 2
  • Cửa sổ [5, 3, 7] \to min = 3
  • Cửa sổ [3, 7, 1] \to min = 1
  • ... và tiếp tục như vậy.

Giới hạn:

  • Subtask #1: n \le 5000 .
  • Subtask #2: n \le 10^6 .