💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Tìm kiếm Giá trị Liền trước
BS013
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `TimGiaTriLienTruoc.inp` | | **Tên File Output** | `TimGiaTriLienTruoc.out` | Các bài làm online các bạn chỉ cần dùng luồng vào/ra chuẩn --- ### 📝 Bài toán 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` <br> `10 4 15 22 4 18 15` <br> `15` <br> `17` <br> `30` <br> `3` <br> `4` | `15` <br> `15` <br> `22` <br> `-1` <br> `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: 17 / 30 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng