Elearning CodePath – CTP Online Judge

Tìm kiếm Giá trị Liền trước

BS013

🟢 Hard #Binary Search #Set / Map

### 📌 Thông tin chung

Cho một mảng $A$ gồm $N$ số nguyên dương.

Yêu cầu: Trả lời $Q$ truy vấn. Mỗi truy vấn là một số nguyên $v$. Đối với mỗi truy vấn $v$, tìm số nguyên **lớn nhất** $a \in A$ thỏa mãn điều kiện:
$a \le v$
Nếu không có số nào trong $A$ thỏa mãn điều kiện trên (tức là $\min(A) > v$), kết quả là $-1$.

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

Dữ liệu vào từ file `TimGiaTriLienTruoc.inp`:

* Dòng 1: Chứa hai số nguyên $N$ và $Q$.
* Dòng 2: Chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
* $Q$ dòng tiếp theo: Mỗi dòng chứa một số nguyên $v$ (truy vấn).

Giới hạn:
* $1 \le N, Q \le 2 \times 10^5$.
* $1 \le A_i \le 10^6$.
* $1 \le v \le 10^6 + 1$.

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

Ghi ra file `TimGiaTriLienTruoc.out` $Q$ dòng. Mỗi dòng là câu trả lời cho truy vấn tương ứng.

---
### ✨ Ví dụ

| Input (`TimGiaTriLienTruoc.inp`) | Output (`TimGiaTriLienTruoc.out`) |
| :--- | :--- |
| `7 5` `10 4 15 22 4 18 15` `15` `17` `30` `3` `4` | `15` `15` `22` `-1` `4` |

Giải thích (Mảng $A$ sau khi sắp xếp và loại trùng lặp: $[4, 10, 15, 18, 22]$):
* $v=15$: Số lớn nhất $\le 15$ là $15$.
* $v=17$: Số lớn nhất $\le 17$ là $15$.
* $v=30$: Số lớn nhất $\le 30$ là $22$ 
---
### 🏷 Phân Subtask

Do $N$ và $Q$ lớn ($2 \times 10^5$), cần thuật toán $O(N \log N + Q \log N)$ (Sắp xếp và $Q$ lần tìm kiếm nhị phân).

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 2000, Q \le 2000$ | $30\%$ |
| 2 | $N \le 2 \times 10^5, Q \le 2 \times 10^5$ | $70\%$ |

---

✅ Đã AC: 8 / 20 submissions