Hướng dẫn giải của Closest Cow Wins

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

Sắp xếp tất cả bãi cỏ và bò Nhoj theo vị trí.
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$ .
Thêm $B$ và $S - B$ vào danh sách lợi ích.
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.

Bình luận

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