---
author: nguyencter
tags: Bwpoints
title: Bwpoints Solution
---

$\Huge\text{Bwpoints Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1xo3Y2jTRMNGvepi5bUBIUgQd1CQByaqP/view?usp=sharing)
📌 Tags: `two pointers`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

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. 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.

**Yêu cầu:** Tìm giá trị k lớn nhất.

-----

## Thuật toán

$\Large N \leq 10^5$

Đầu tiên ta sắp xếp mảng a và mảng b theo thứ tự tăng dần.

Sử dụng 2 con trỏ x và y: đặt con trỏ x vào mảng có phần tử nhỏ nhất là lớn nhất còn con trỏ y thì đặt vào mảng còn lại.

Ban đầu vị trí con trỏ x và y đều bằng một.

Nếu phần tử ở vị trí con trỏ x lớn hơn hoặc bằng phần tử ở vị trí con trỏ y thì tăng biến kết quả lên một đơn vị đồng thời tăng vị trí con trỏ x và vị trí con trỏ y lên một đơn vị.

Ngược lại tăng vị trí con trỏ x lên một đơn vị.

Tiếp tục cho đến khi vị trí con trỏ x hoặc vị trí con trỏ y lớn hơn n thì in ra biến kết quả

----

Đpt $O(n)$.

Tham khảo code ở [đây](https://github.com/nguyencter/CODE/blob/main/bwpoints.cpp)