Elearning CodePath – CTP Online Judge

Số trung vị

MEDIAN

🟢 Easy #Priority Queue #Interval #Data Structure

### 📌 Thông tin chung

### 📝 Bài toán

Cho một dãy số ban đầu rỗng. Bạn sẽ lần lượt nhận được $n$ số nguyên $a_1, a_2, \dots, a_n$. Với mỗi số $a_i$ nhận được, bạn phải thực hiện:
1. Thêm $a_i$ vào dãy số hiện tại.
2. Tính số trung vị (median) của dãy số mới cập nhật.

Định nghĩa số trung vị của một dãy sau khi đã sắp xếp:
* Nếu độ dài dãy là lẻ (kích thước $m$): Median là phần tử ở vị trí giữa.
* Nếu độ dài dãy là chẵn (kích thước $m$): Median là trung bình cộng của hai phần tử ở giữa.

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file MEDIAN.INP:
* Dòng 1: Số nguyên dương $n$.
* $n$ dòng tiếp theo: Mỗi dòng chứa một số nguyên $a_i$.

### 📤 Định dạng Đầu ra

Ghi ra file MEDIAN.OUT gồm $n$ dòng, mỗi dòng là một số thực biểu diễn median của dãy tại bước đó, định dạng 1 chữ số thập phân sau dấu phẩy.

### ✨ Ví dụ

| MEDIAN.INP | MEDIAN.OUT |
| :--- | :--- |
| 6 12 4 5 3 8 7 | 12.0 8.0 5.0 4.5 5.0 6.0 |

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $n \le 1000, a_i \le 10^5$ | 30% |
| 2 | $n \le 10^5, a_i \le 10^5$ | 70% |

✅ Đã AC: 5 / 7 submissions