KHẢO SÁT ĐỘI TUYỂN K12 LẦN 3
Mô tả bài toán:
Có ~ n ~ khách sạn trên một con đường. Với mỗi khách sạn, bạn biết số lượng phòng trống. Nhiệm vụ của bạn là phân bổ phòng khách sạn cho các nhóm du khách. Mỗi nhóm du khách yêu cầu toàn bộ thành viên của họ ở trong cùng một khách sạn.
Các nhóm sẽ lần lượt đến, và bạn biết số lượng phòng mà mỗi nhóm yêu cầu. Bạn luôn phân bổ nhóm vào khách sạn đầu tiên có đủ số phòng trống. Sau khi phân bổ, số lượng phòng trống tại khách sạn đó sẽ giảm đi theo số phòng đã sử dụng. Nếu không có khách sạn nào đủ phòng, nhóm sẽ không được phân bổ.
Input:
- Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ m ~: số lượng khách sạn và số lượng nhóm du khách.
- Dòng thứ hai chứa ~ n ~ số nguyên ~ h_1, h_2, \ldots, h_n ~: số lượng phòng trống ở mỗi khách sạn.
- Dòng cuối cùng chứa ~ m ~ số nguyên ~ r_1, r_2, \ldots, r_m ~: số lượng phòng mà mỗi nhóm yêu cầu.
Output:
- In ra số khách sạn được phân bổ cho từng nhóm. Nếu một nhóm không được phân bổ vào bất kỳ khách sạn nào, in ra
0
cho nhóm đó.
Ràng buộc:
- ~ 1 \leq n, m \leq 2 \cdot 10^5 ~
- ~ 1 \leq h_i \leq 10^9 ~
- ~ 1 \leq r_i \leq 10^9 ~
Ví dụ:
Input:
8 5
3 2 4 1 5 5 2 6
4 4 7 1 1
Output:
3 5 0 1 1
Giải thích:
- Nhóm 1 cần 4 phòng. Họ được phân vào khách sạn 3 (khách sạn đầu tiên có ít nhất 4 phòng trống).
- Nhóm 2 cần 4 phòng. Họ được phân vào khách sạn 5.
- Nhóm 3 cần 7 phòng. Không có khách sạn nào đủ phòng, nhóm này không được phân bổ (
0
). - Nhóm 4 cần 1 phòng. Họ được phân vào khách sạn 1 (còn 2 phòng trống sau khi nhóm này được phân bổ).
- Nhóm 5 cần 1 phòng. Họ được phân vào khách sạn 1 (còn 1 phòng trống sau khi nhóm này được phân bổ).