Hướng dẫn giải của Bò chen chúc

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Bò chen chúc

Hướng tiếp cận

Sắp xếp các con bò theo vị trí, sau đó dùng hai cửa sổ trượt (sliding window) với multiset để theo dõi chiều cao lớn nhất bên trái và bên phải trong khoảng cách $D$ .

Nhận xét quan trọng

Sau khi sắp xếp theo vị trí, ta có thể duyệt từ trái sang phải và duy trì hai multiset:
- Multiset X: chứa chiều cao các bò trong khoảng $[x_{i} - D, x_{i})$ (bên trái).
- Multiset Y: chứa chiều cao các bò trong khoảng $(x_{i}, x_{i} + D]$ (bên phải).
Phần tử lớn nhất trong multiset chính là phần tử cuối, kiểm tra trong $O (\log N)$ .

Thuật toán

Sắp xếp $N$ bò theo vị trí tăng dần.
Duyệt từ trái sang phải. Duy trì hai con trỏ $j$ (biên trái cho multiset X) và $k$ (biên phải cho multiset Y).
Với mỗi bò i:
- Thêm các bò vào Y cho đến khi vượt quá $x_{i} + D$ .
- Loại các bò ra khỏi X nếu khoảng cách vượt quá $D$ .
- Thêm bò $i$ vào X.
- Kiểm tra: max(X) $\geq 2 h_{i}$ VÀ max(Y) $\geq 2 h_{i}$ .
- Loại bò $i$ khỏi Y.
Đếm tổng số bò thỏa mãn.

Độ phức tạp

Thời gian: $O (N \log N)$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.