Chọn bạn nhảy
Đề bài
Câu lạc bộ khiêu vũ của trường có m bạn nam được đánh số từ 1 đến m và n bạn nữ được đánh số từ 1 đến n đăng ký tham gia. Bạn nam thứ i có chiều cao aᵢ (1 ≤ i ≤ m), bạn nữ thứ j có chiều cao bⱼ (1 ≤ j ≤ n). Để xây dựng đội hình biểu diễn, câu lạc bộ cần chọn k cặp bạn nhảy. Mỗi cặp gồm đúng một bạn nam và một bạn nữ, đồng thời mỗi người chỉ được ghép vào một cặp duy nhất.
Chỉ số phù hợp của một cặp là giá trị tuyệt đối của hiệu chiều cao giữa hai người: |aᵢ − bⱼ|
Chỉ số phù hợp của cả đội hình được xác định bằng chỉ số phù hợp lớn nhất trong tất cả các cặp đã chọn.
Yêu cầu: Hãy chọn k cặp bạn nhảy sao cho chỉ số phù hợp của đội hình là nhỏ nhất.
Dữ liệu: Đọc từ tệp văn bản DANS.INP:
- Dòng đầu tiên chứa ba số nguyên dương m, n, k (k ≤ min(m, n), m, n ≤ 105).
- Dòng thứ hai chứa m số nguyên dương a₁, a₂, ..., aₘ (aᵢ ≤ 109).
- Dòng thứ ba chứa n số nguyên dương b₁, b₂, ..., bₙ (bⱼ ≤ 109).
Kết quả: Ghi ra tệp văn bản DANS.OUT một số nguyên duy nhất là chỉ số phù hợp nhỏ nhất của đội hình gồm k cặp bạn nhảy.
Ví dụ
4 4 2 160 165 170 175 162 163 168 172
2
3 4 3 150 155 160 152 153 154 165
5
Ràng buộc & Tóm tắt
-
Có 30% số test, tương ứng 30% số điểm, thỏa mãn: m, n ≤ 103, k = 1.
Có 30% số test, tương ứng 30% số điểm, thỏa mãn: m, n ≤ 105, k = 1.
40% số test còn lại, tương ứng 40% số điểm, không có ràng buộc nào thêm.
