1. CẤU TRÚC ĐỀ BÀI
- Tên
bài: GIAO ĐẤU
- Mã
bài: MATCH
- File
chương trình: MATCH.PY
- File
dữ liệu: MATCH.INP
- File
kết quả: MATCH.OUT
2. Dẫn dắt
Để tạo không khí sôi nổi cho kỳ thi OLP-ACM sắp tới, ban tổ
chức đề xuất một trận giao hữu game online tay đôi giữa sinh viên trường chủ
nhà và trường khách. Mỗi trường cử ra một đội gồm N thành viên để thi đấu đối
kháng 1-1.
Trong trò chơi này, kết quả thắng thua phụ thuộc hoàn toàn
vào chỉ số năng lực: người có năng lực cao hơn sẽ thắng và được 1 điểm, người
thua được 0 điểm (các trường hợp hòa hoặc hết giờ không được tính điểm).
Trưởng đoàn trường chủ nhà có danh sách năng lực của cả hai
đội và có quyền sắp xếp ai đấu với ai. Bạn hãy giúp họ bố trí cặp đấu để đạt tổng
điểm cao nhất.
3. Yêu cầu
Cho hai dãy số nguyên dương A (đội khách) và B (đội chủ nhà)
đều có N phần tử. Hãy tìm cách ghép cặp sao cho số lượng phần tử của B thắng phần
tử tương ứng của A là lớn nhất.
4. Dữ liệu (Input)
- Dòng
1: Chứa số nguyên dương N (1 ≤ N ≤ 100.000).
- Dòng
2: Chứa N số nguyên dương là năng lực của đội khách (1 ≤ Ai ≤ 10⁹).
- Dòng
3: Chứa N số nguyên dương là năng lực của đội chủ nhà (1 ≤ Bi ≤ 10⁹).
5. Kết quả (Output)
- Ghi
ra một số nguyên duy nhất là tổng điểm lớn nhất đội chủ nhà có thể đạt được.
6. Ví dụ
|
MATCH.INP |
MATCH.OUT |
Giải thích |
|
5 10 15 30 20 25 28 24 20 16 14 |
4 |
Sắp xếp lại: - Khách: 10, 15, 20, 25, 30 - Nhà: 14, 16, 20, 24, 28 Ghép cặp: - 14 thắng 10 - 16 thắng 15 - 24 thắng 20 - 28 thắng 25 - 20 thua 30 Tổng: 4 trận thắng. |
7.
Ràng buộc
- 30%
số test: N ≤ 10
- 60%
số test: N ≤ 2.000
- 100%
số test: N ≤ 100.000. Các chỉ số năng lực ≤ 10⁹
Tải test chấm Themis
1.gif)