Trung vị đoạn tịnh tiến
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho mảng gồm ~n~ số nguyên. Yêu cầu tính giá trị trung vị cho từng cửa sổ (đoạn con) gồm ~k~ phần tử liên tiếp, xét lần lượt từ trái sang phải.
Giá trị trung vị được xác định là vị trí chính giữa sau khi dãy đã sắp xếp. Nếu kích thước cửa sổ ~k~ là số chẵn, trung vị được quy ước là số nhỏ hơn trong hai phần tử nằm ở giữa.
Input
- Dòng đầu tiên gồm hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 2 \cdot 10^5~) biểu thị số lượng phần tử và kích thước đoạn con.
- Dòng tiếp theo chứa ~n~ số nguyên ~x_1, x_2, \dots, x_n~ (~1 \le x_i \le 10^9~) là các phần tử trong mảng.
Output
- In ra ~n - k + 1~ giá trị trung vị tìm được trên cùng một dòng, phân tách bởi khoảng trắng.
Example
Input:
8 3
2 4 3 5 8 1 2 1
Output:
3 4 5 5 2 1
Bình luận