VOI 11 Bài 4 - Nối điểm đen trắng

Điểm: 0,09 (OI)

Giới hạn thời gian: 0.6s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

VOI 2011

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trên trục số thực cho ~n~ điểm đen và ~n~ điểm trắng hoàn toàn phân biệt. Các điểm đen có tọa độ nguyên ~a_1, a_2, ..., a_n~ còn các điểm trắng có tọa độ nguyên ~b_1, b_2, ..., b_n~. Người ta muốn chọn ra ~k~ điểm đen và ~k~ điểm trắng để nối mỗi một điểm đen với một điểm trắng sao cho ~k~ đoạn thẳng tạo được đôi một không có điểm chung.

Kết quả: Ghi ra một số nguyên duy nhất là số ~k~ lớn nhất tìm được

Input

Dòng thứ nhất chứa số nguyên dương ~n\; (n \leq 10^5)~.
Dòng thứ hai chứa các số ~a_1, a_2, ..., a_n\; (|a_i| \leq 10^9, i = 1, 2,..., n)~.
Dòng thứ ba chứa các số ~b_1, b_2, ..., b_n\; (|b_i| \leq 10^9, i = 1, 2,..., n)~.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Cho tọa độ của ~n~ điểm đen ~a_1, a_2, ..., a_n~ và tọa độ của điểm trắng ~b_1, b_2, ..., b_n~. Hãy tìm giá trị ~k~ lớn nhất thỏa mãn yêu cầu trên.

Giới hạn

50% số test ứng với 50% số điểm của bài có ~1 \leq n \leq 100~

Sample Input

3
0 3 1
-3 5 -1

Sample Output

Note

Bình luận

Hãy đọc nội quy trước khi bình luận.

8

dangminh đã bình luận lúc 27, Tháng 6, 2025, 4:12

Hint bài này:

a[i], b[i] gom lại 1 nhóm lưu kiểu (giá trị, loại)

sort nhóm chung dựa trên giá trị

có thể dùng struct hoặc pair<int,int>

duyệt từ 1->2n-1 so sánh loại i khác i + 1 -> một cặp điểm rồi bỏ qua i + 1 vì đã ghép với i

vominhmanh10 đã bình luận lúc 25, Tháng 11, 2025, 3:55

gom mảng a và b và sắp sếp tăng dần theo cặp như ý tưởng trên

import sys
input = sys.stdin.readline

def solve():
    n = int(input().strip())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = []
    for x in a: c.append((x, 0))
    for x in b: c.append((x, 1))
    c.sort()
    i = 0
    res = 0
    while i < 2 * n - 1:
        if c[i][1] != c[i + 1][1]: 
            res += 1
            i += 1
        i += 1
    print(res)
if __name__ == "__main__":
    solve()

3

ChiPhatNguyen đã bình luận lúc 13, Tháng 8, 2025, 4:36

nhờ anh này mà em mới làm full đc :3 thank you!