Bò chen chúc

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

1. 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).
2. 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

1. Sắp xếp $N$ bò theo vị trí tăng dần.
2. 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).
3. 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) $\ge 2h_i$ VÀ max(Y) $\ge 2h_i$.
   • Loại bò $i$ khỏi Y.
4. Đếm tổng số bò thỏa mãn.

Độ phức tạp

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