Chọn đũa
Đề bài
An có $n$ chiếc đũa màu xanh có độ dài lần lượt là $a_1, a_2, \ldots, a_n$ và $n$ chiếc đũa màu đỏ có độ dài lần lượt là $b_1, b_2, \ldots, b_n$ $(1 \le a_i, b_i \le 10^9$; $1 \le i \le n$; $1 \le n \le 10^5)$. An muốn chọn một chiếc đũa màu xanh và một chiếc đũa màu đỏ để ghép thành một đôi. Các đôi đũa được xem là khác nhau khi tất cả các chiếc đũa được chọn phải khác nhau.
Yêu cầu: tính số lượng đôi đũa An có thể lấy sao cho độ dài các chiếc đũa trong một đôi bằng nhau.
Dữ liệu vào: từ file văn bản CHONDUA.INP có cấu trúc như sau:
- Dòng đầu ghi số nguyên dương $n$;
- Dòng thứ hai ghi $n$ số nguyên $a_1, a_2, \ldots, a_n$;
- Dòng thứ ba ghi $n$ số nguyên $b_1, b_2, \ldots, b_n$.
Kết quả: ghi ra file CHONDUA.OUT gồm một số duy nhất là kết quả tính được.
Giải thích ví dụ: An có thể lấy 1 đôi đũa độ dài 2; 2 đôi đũa độ dài 3 và 1 đôi đũa độ dài 4.
Lưu ý: đề gốc đọc/ghi file CHONDUA.INP / CHONDUA.OUT; trên CLUE OJ và Codeforces thì dùng stdin/stdout. Code bên dưới chạy được cả hai kiểu.
5
2 3 4 3 3
1 2 3 4 34Lời mở đầu
Bài này ngắn nhưng câu chữ "các đôi đũa được xem là khác nhau khi tất cả các chiếc đũa được chọn phải khác nhau" làm nhiều bạn hiểu nhầm. Ý của đề là: mỗi chiếc đũa chỉ được dùng tối đa một lần, hỏi ghép được nhiều nhất bao nhiêu đôi cùng độ dài. Nếu hiểu nhầm thành "đếm số cặp $(i, j)$ có $a_i = b_j$" thì ví dụ sẽ ra $1 + 3 \cdot 2 + 1 = 8$ chứ không phải 4 đâu nhé!
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | n | Độ dài lớn nhất | Đáp án | Mức |
|---|---|---|---|---|
| 1 – 6 | 10 – 1.326 | 9.999 | 4 – 185 | Mức 1 |
| 7 | 7.456 | 32.768 | 1.413 | Mức 2 |
| 8 – 10 | 84.325 – 98.467 | 32.768 | 55.331 – 67.103 | Mức 3 |
Bộ test có 10 test. Đề không chia subtask, nhưng nhìn vào $n$ thì thấy rõ 3 mức độ nên mình tự chia như bảng trên để so sánh các cách giải. Vài điều đáng chú ý:
- Đề cho độ dài tới $10^9$, nhưng trong test thật độ dài lớn nhất chỉ là 32.768. Tuy vậy mình vẫn viết code theo đúng giới hạn của đề (dùng
maphoặc sắp xếp), không "ăn may" vào dữ liệu. - Ở mức 3, có khoảng 30.000 độ dài khác nhau cho $10^5$ chiếc đũa mỗi màu, tức mỗi độ dài lặp lại khoảng 3 lần – đáp án vào khoảng 55.000–67.000 đôi.
| Mức | Test | Cách 1 ghép tay | Cách 2 map | Cách 3 sort |
|---|---|---|---|---|
| 1 | 1–6 | ✔ | ✔ | ✔ |
| 2 | 7 | ✔ | ✔ | ✔ |
| 3 | 8–10 | ✘ TLE | ✔ | ✔ |
Ý tưởngMỗi độ dài ghép được min(số xanh, số đỏ) đôi
Đũa độ dài 3 chỉ ghép được với đũa độ dài 3, chẳng liên quan gì tới đũa độ dài khác. Vậy ta xét riêng từng độ dài $d$: nếu có $c_A$ chiếc xanh và $c_B$ chiếc đỏ dài $d$, thì ghép tối đa được $\min(c_A, c_B)$ đôi (bên ít hơn dùng hết, bên nhiều hơn thừa ra).
Em nhập độ dài các đũa rồi bấm Tiếp để xem ghép từng nhóm độ dài:
Vấn đề còn lại chỉ là đếm $c_A[d]$ và $c_B[d]$ thế nào cho nhanh. Mình đi lần lượt 3 cách.
Mức 1–2Cách 1: ghép tay từng chiếc
Làm đúng như ngoài đời: cầm từng chiếc đũa xanh, lục trong đống đũa đỏ tìm một chiếc cùng độ dài chưa bị lấy. Tìm thấy thì ghép (đánh dấu chiếc đỏ đã dùng), không thấy thì bỏ chiếc xanh đó. Cách tham lam này cho đúng $\min(c_A, c_B)$ đôi ở mỗi độ dài.
- Mảng
used[j]đánh dấu chiếc đỏ thứ $j$ đã nằm trong một đôi, để không dùng 2 lần. - Lệnh
breakrất quan trọng: tìm được 1 chiếc đỏ rồi thì dừng ngay, nếu không một chiếc xanh sẽ "ôm" nhiều chiếc đỏ.
Kết quả chạy thật (mình đo thời gian CPU, giới hạn 1 giây): bản C++ đúng 7/10 test (hết mức 1 và mức 2, test 7 với $n = 7456$ chỉ mất 0.07 giây); 3 test mức 3 có $n \approx 10^5$ thì quá thời gian, vì những chiếc xanh không có cặp phải lục hết $10^5$ chiếc đỏ – tổng cộng cỡ $3 \cdot 10^9$ phép so sánh. Bản Python chậm hơn nhiều, đúng 6/10 test và quá thời gian ngay từ test 7.
100%Cách 2: đếm bằng map
Thay vì lục tìm, mình dùng map<int, int> cnt làm "kho đũa xanh": cnt[d] = số đũa xanh dài $d$ còn trong kho. Sau đó duyệt từng chiếc đỏ dài $y$: nếu kho còn đũa xanh dài $y$ thì lấy ra một chiếc ghép đôi (cnt[y]--, ans++). Như vậy ở mỗi độ dài, số đôi ghép được đúng bằng $\min(c_A, c_B)$.
- Độ dài tới $10^9$ nên không dùng mảng đếm theo chỉ số được,
mapchỉ lưu những độ dài thật sự xuất hiện. - Câu lệnh
if (cnt[y] > 0): nếu $y$ chưa có trong map thì toán tử[]tự thêm khoá $y$ với giá trị 0, điều kiện sai, không sao cả. Trong khung chạy tay bên dưới các bạn sẽ thấy khoá mới "0" xuất hiện như vậy. - Không cần đọc trước cả dãy $b$: đọc chiếc nào xử lý chiếc đó luôn.
Kết quả chạy thật: đúng 10/10 test, thời gian CPU lớn nhất 0.10 giây. Bản Python dùng dict cũng đúng 10/10, chậm nhất 0.16 giây.
100%Cách 3: sắp xếp + hai con trỏ
Một cách khác không cần map: sắp xếp cả hai dãy tăng dần, đặt con trỏ $i$ ở đầu dãy xanh, $j$ ở đầu dãy đỏ.
- Nếu $a_i = b_j$: ghép được 1 đôi, cả hai con trỏ cùng tiến.
- Nếu $a_i < b_j$: chiếc xanh $a_i$ ngắn hơn mọi chiếc đỏ còn lại (vì dãy đỏ đã tăng dần), nó không bao giờ có cặp → bỏ, $i$ tiến.
- Ngược lại $a_i > b_j$: chiếc đỏ $b_j$ không có cặp → $j$ tiến.
Kết quả chạy thật: đúng 10/10 test, thời gian CPU lớn nhất 0.04 giây; bản Python 10/10, chậm nhất 0.20 giây.
map) và cách 3 (sort + hai con trỏ): đều 10/10 với cả C++ và Python. Đề ghi độ dài tới $10^9$ nhưng test thật chỉ tới 32.768.
Nhận xét
Đăng nhận xét