Hướng dẫn giải của Leo Núi

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: Leo Núi

Hướng tiếp cận

Sắp xếp tối ưu thứ tự người leo rồi mô phỏng tham lam. Chia người thành hai nhóm theo quan hệ $U$ và $D$ , sau đó sắp xếp mỗi nhóm theo tiêu chí phù hợp để tối thiểu hoá tổng thời gian.

Nhận xét quan trọng

Nhóm "nhanh lên, chậm xuống" ( $U < D$ ): nếu leo lên trước, thời gian chờ trên đỉnh ngắn hơn — nên xếp theo $U$ tăng dần.
Nhóm "chậm lên, nhanh xuống" ( $U \geq D$ ): nếu leo xuống trước (sau khi lên xong), thời gian lãng phí nhỏ hơn — nên xếp theo $D$ giảm dần.
Tất cả người trong nhóm $U < D$ đều nên leo trước nhóm $U \geq D$ .
Sau khi có thứ tự tối ưu, mô phỏng: duy trì up_end (thời điểm đường lên rảnh) và down_end (thời điểm đường xuống rảnh).

Thuật toán

Chia người thành hai nhóm: nhóm A ( $U_{i} < D_{i}$ ) và nhóm B ( $U_{i} \geq D_{i}$ ).
Sắp xếp nhóm A theo $U_{i}$ tăng dần, nhóm B theo $D_{i}$ giảm dần.
Ghép: tất cả nhóm A trước, nhóm B sau.
Mô phỏng theo thứ tự đã sắp:
- Người thứ $i$ bắt đầu leo lên lúc up_end. Lên đến đỉnh lúc up_end + U_i.
- Người này bắt đầu leo xuống lúc max(up_end + U_i, down_end). Xuống xong lúc start_down + D_i.
- Cập nhật up_end += U_i, down_end = start_down + D_i.
Đáp án là down_end sau khi xử lý tất cả.

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