Closest Cow Wins

Lời giải: Closest Cow Wins

Hướng tiếp cận

Bò của Nhoj chia trục số thành các đoạn. Trong mỗi đoạn giữa hai bò liên tiếp của Nhoj, FJ có thể chiếm tất cả bãi cỏ bằng $1$ bò (nếu đặt ở giữa đoạn), hoặc chiếm nửa tốt nhất bằng $1$ bò.

Thuật toán

1. Sắp xếp tất cả bãi cỏ và bò Nhoj theo vị trí.
2. Với mỗi đoạn giữa $2$ bò Nhoj liên tiếp, tính tổng $S$ và giá trị lớn nhất chiếm được bằng $1$ bò $B$.
3. Thêm $B$ và $S-B$ vào danh sách lợi ích.
4. Sắp xếp danh sách giảm dần, lấy $N$ phần tử lớn nhất.

Độ phức tạp

$O((K+M)\log (K+M))$ thời gian.