Bedao Regular Contest 10 - VOLUNTEERS
Xem dạng PDFĐợt tuyển tình nguyện viên lần thứ ~2~ của VNOI đã diễn ra thành công và tốt đẹp. Những TNV được chọn ra đều là những gương mặt ưu tú nhất, để kiểm tra khả năng của TNV, các admin đã chuẩn bị một bài kiểm tra như sau:
Admin có ~n~ công việc, các công việc được đánh số từ ~1~ đến ~n~ tương ứng với độ khó lần lượt ~a_1, a_2, a_3, \dots, a_n~. Có ~m~ tình nguyện viên, mỗi tình nguyện viên cũng được đánh số từ ~1~ đến ~m~ tương ứng với khả năng làm được công việc độ khó lần lượt là ~b_1, b_2, b_3, \dots, b_m~. Các TNV đều là những người hăng hái ai cũng muốn chọn công việc có độ khó cao nhất (nhưng không vượt quá khả năng của mình) . Các TNV lần lượt từ trái sang phải đi nhận từng công việc, mỗi công việc chỉ được chọn ~1~ lần , nếu không có công việc nào phù hợp với khả năng của mình thì TNV đó sẽ được nghỉ.
Sau ~m~ lượt, có thể còn lại những công việc không được chọn bởi ai cả, nhiệm vụ của bạn là tìm công việc có độ khó cao nhất, nếu không còn lại công việc nào thì in ra ~-1~.
Input
Gồm ~3~ dòng chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^{6})~.
Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, a_3, \dots, a_n~ ~(1 \le a_i \le 10^{9})~ tương ứng là độ khó của từng công việc.
Dòng thứ ba gồm ~m~ số nguyên dương ~b_1, b_2, b_3, \dots, b_m~ ~(1 \le b_i \le 10^{9})~ tương ứng là năng lực của từng TNV.
Output
Gồm một số nguyên duy nhất là yêu cầu của bài toán.
Subtask
- ~20\%~ số test có ~1 \le a_i \le 5000~
- ~80\%~ số test còn lại không có điều kiện gì thêm
Sample Input
4 6
1 8 2 4
3 3 6 1 5 2
Sample Output
8
Note
Quy trình chọn việc từ trái qua phải như sau :
- Người ~1~ có khả năng làm công việc có độ khó cao nhất là ~3~ chọn công việc thứ ~3~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(2 \le 3)~ , loại công việc thứ ~3~ ra khỏi danh sách.
Danh sách công việc còn lại có thể chọn là ~[1, 8, 4]~.
- Người ~2~ có khả năng làm công việc có độ khó cao nhất là ~3~ chọn công việc thứ ~1~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(1 \le 3)~ , loại công việc thứ ~1~ ra khỏi danh sách.
Danh sách công việc còn lại có thể chọn là ~[8, 4]~.
- Người ~3~ có khả năng làm công việc có độ khó cao nhất là ~6~ chọn công việc thứ ~4~ có độ khó cao nhất nhưng không vượt quá khả năng của mình ~(4 \le 6)~ , loại công việc thứ ~4~ ra khỏi danh sách.
Danh sách công việc còn lại có thể chọn là ~[8]~.
- Ba người còn lại không thể chọn được công việc nào vì công việc có thể chọn còn lại vượt quá khả năng của ~3~ người đó.
Vậy công việc lớn nhất còn lại là ~8~.
Bình luận
anh em giải thích giúp mình với sao lại bị runtime với segmentation error nhỉ
Cách giải khác với cách giải của admin và đơn giản hơn nhiều.
nhưng nếu làm thế thì độ phức tạp sẽ là o(n log n+m log m) nên tất nhiên là cách làm của ad vẫn hay hơn rồi
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.