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

Bình luận

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

duongoi281012 đã bình luận lúc 3, Tháng 2, 2026, 17:15

sử dụng 2 con trỏ + tham lam

#include <bits/stdc++.h>
#define faster ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ld long double
#define ll long long
#define endl '\n'
#define fi(i, a, b) for(int i = (a); i <= (b); i++)
#pragma GCC optimize ("unroll-loops", "O3", "Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
int n;
int main()
{
    int res = 0;
    int last = -1e9;
    cin >> n;
    int a[n + 1], b[n + 1];
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    int l = 1, r = 1;
    while(l <= n && r <= n)
    {
        if(min(a[l], b[r]) > last) {res++; last = max(a[l], b[r]); r++; l++;}
        else
        {
            if(a[l] < b[r]) l++;
            else r++;
        }
    }
    cout << res;
}

lưu ý: luôn cố gắng giữ phần sử dụng độ dài là ngắn nhất và nếu a[l] < b[r] thì ta nên l++ để tối ưu thay vì tốn thêm khoảng cách khi tăng r

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()

2

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!