HSG9 Cà Mau 2026 - Tặng quà
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Ban tổ chức hội trại có chuẩn bị các món quà lưu niệm dành tặng cho các trại sinh trong đợt tham gia hội trại. Có ~N~ món quà, với món quà thứ ~i~ sẽ có cân nặng ~P_i~ (với mỗi món quà ở vị trí ~i~, ban tổ chức có thể phát cho nhiều trại sinh nhưng một trại sinh không thể nhận nhiều hơn hoặc bằng ~2~ lần cùng một món quà ở vị trí ~i~).
Trong hội trại, có ~Q~ trại sinh và mỗi trại sinh có thể mang theo ~X~ cân nặng. Ban tổ chức cần hướng dẫn các bạn trại sinh một lựa chọn sao cho nhận được nhiều món quà nhất có thể.
Yêu cầu: Có ~Q~ trại sinh, với trại sinh thứ ~j~ có thể mang theo ~X_j~ cân nặng. Hãy giúp ban tổ chức tính số lượng quà tối đa mà trại sinh có thể nhận được.
Input
Dòng ~1~: Hai số nguyên dương ~N~ và ~Q~ (~0 \le N, Q \le 10^5~);
Dòng ~2~: ~N~ số nguyên dương ~P_i~ (~1 \le P_i \le 10^4~);
~Q~ dòng tiếp theo: mỗi dòng một số ~X_j~ (~1 \le X_j \le 10^9~).
Output
~Q~ dòng, mỗi dòng là số quà tối đa nhận được.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~40\%~ | ~0 \le N, Q \le 10^3~, ~1 \le P_i \le 10^2~, ~1 \le X_j \le 10^3~; |
| 2 | ~40\%~ | ~10^3 \le N, Q \le 10^5~, ~10^2 \le P_i \le 10^4~, ~10^3 \le X_j \le 10^5~; |
| 3 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
5 3
5 2 4 1 3
6
1
14
Sample Output 1
3
1
4
Notes
Có ~3~ trại sinh với phương án tối ưu được chọn như sau:
Với cân nặng ~X = 6~: Nhận được số quà tối đa ~3~ (~2 + 1 + 3 = 6~).
Với cân nặng ~X = 1~: Nhận được số quà tối đa ~1~ (~1 = 1~).
Với cân nặng ~X = 14~: Nhận được số quà tối đa ~4~ (~2 + 4 + 1 + 3 = 10~).
Bình luận
include <bits/stdc++.h>
PHÂN TÍCH BÀI TOÁN VÀ GIẢI THUẬT: TẶNG QUÀ
1. Phân tích bài toán
2. Giải thuật chi tiết
Bước 1: Đọc dữ liệu và sắp xếp
sort(a + 1, a + n + 1)):Bước 2: Xây dựng mảng cộng dồn (Prefix Sum)
prevớipre[i]lưu tổng trọng lượng của $i$ món quà nhẹ nhất sau khi đã sắp xếp: $$\text{pre}[i] = \text{pre}[i-1] + a[i]$$precó tính chất tăng dần, giúp ta nhanh chóng biết được tổng trọng lượng khi lấy $i$ món quà nhẹ nhất.Bước 3: Xử lý các truy vấn với Tìm kiếm nhị phân (Binary Search)
upper_bound(pre + 1, pre + n + 1, x)để tìm vị trí đầu tiên có tổng trọng lượng lớn hơn $X$.prevà trừ tiếp đi $1$ (- pre - 1), ta thu được số lượng món quà tối đa có thể chọn (it).3. Đánh giá độ phức tạp
upper_boundmất $O(\log N)$. Với $Q$ truy vấn, tổng thời gian xử lý truy vấn là $O(Q \log N)$.