Elearning CodePath – CTP Online Judge

Phân cặp Đấu tối ưu

GRD002

🟢 Easy #Greedy #Sorting #Two Pointers #Interval

### 📌 Thông tin chung

---
### 📝 Quy tắc Trò chơi và Mục tiêu

* Hai đội, mỗi đội $N$ người. Đội $A$ (trường đề xuất) và Đội $B$ (trường sở tại).
* Mỗi người $i$ có chỉ số năng lực $A_i$ hoặc $B_i$.
* Quy tắc đấu: Người có năng lực **cao hơn** sẽ thắng (1 điểm). Người có năng lực **thấp hơn** sẽ thua (0 điểm). Hòa (năng lực bằng nhau) bị hủy kết quả (0 điểm).
* Mục tiêu: Trưởng đoàn Đội $B$ phải phân cặp đấu sao cho **tổng số điểm Đội $B$ thu được là lớn nhất**.

---
### 📝 Bài toán

Cho hai dãy năng lực $A = (A_1, \dots, A_n)$ và $B = (B_1, \dots, B_n)$. Phân cặp $N$ người của $A$ với $N$ người của $B$ thành $N$ cặp duy nhất $(A_i, B_j)$ để tối đa hóa số lượng cặp mà $B_j > A_i$.

---
### 📥 Định dạng Đầu vào

Đọc từ tập tin `GIDA.INP`:

* Dòng 1: Chứa số nguyên $N$ (số người mỗi đội).
* Dòng 2: Chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ (chỉ số năng lực đội $A$).
* Dòng 3: Chứa $N$ số nguyên $B_1, B_2, \dots, B_N$ (chỉ số năng lực đội $B$).

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le A_i, B_i \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra tập tin `GIDA.OUT` một số nguyên duy nhất là số điểm tối đa Đội $B$ có thể đạt được.

---
### ✨ Ví dụ

| GIDA.INP | GIDA.OUT |
| :---: | :---: |
| `5` <br> `10 15 30 20 25` <br> `28 24 20 16 14` | `4` |

**Giải thích Ví dụ:**

* Đội $A$: $A' = (10, 15, 20, 25, 30)$ (Sắp xếp tăng dần).
* Đội $B$: $B' = (14, 16, 20, 24, 28)$ (Sắp xếp tăng dần).

**Cách phân cặp tối ưu (Đội B thắng 4 trận):**
1.  $B_{28}$ thắng $A_{25}$ (28 > 25)
2.  $B_{24}$ thắng $A_{20}$ (24 > 20)
3.  $B_{20}$ thắng $A_{15}$ (20 > 15)
4.  $B_{16}$ thắng $A_{10}$ (16 > 10)
5.  $B_{14}$ đấu $A_{30}$ (14 < 30) $\to$ $B$ thua.

---

✅ Đã AC: 0 / 0 submissions