Leo Núi

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

1. 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.
2. Nhóm "chậm lên, nhanh xuống" ($U\ge 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.
3. Tất cả người trong nhóm $U<D$ đều nên leo trước nhóm $U\ge D$.
4. 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

1. Chia người thành hai nhóm: nhóm A ($U_i<D_i$) và nhóm B ($U_i\ge D_i$).
2. Sắp xếp nhóm A theo $U_i$ tăng dần, nhóm B theo $D_i$ giảm dần.
3. Ghép: tất cả nhóm A trước, nhóm B sau.
4. 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.
5. Đá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)$