ICPC PTIT 2025 - Problem J
Xem PDF
Điểm:
1600 (p)
Thời gian:
0.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Một khu du lịch có \(n\) hòn đảo, hòn đảo \(i\) có độ cao \(h_i\).
Để di chuyển từ hòn đảo \(i\) đến hòn đảo \(j\), du khách có thể sử dụng tàu lượn với chi phí:
\[
cost_{i \to j} = \max(0, h_j - h_i)
\]
Tuy nhiên, sau một thời gian, các nhà thầu đã áp dụng giá sàn thuê tàu lượn cho mỗi đảo \(i\) là \(p_i\). Khi đó, chi phí mới để bay từ \(i\) đến \(j\) là:
\[
cost_{i \to j} = \max(p_i, h_j - h_i)
\]
Nhiệm vụ
Một du khách muốn thăm tất cả \(n\) hòn đảo, bắt đầu từ một hòn đảo, sử dụng tàu lượn để đến các đảo khác theo thứ tự tùy ý. Sau đó quay lại đảo xuất phát.
Tính tổng chi phí nhỏ nhất để hoàn thành hành trình.
Input
- Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\).
- \(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm \(h_i\) và \(p_i\)
\((0 \le h_i, p_i \le 10^9)\).
Output
- Ghi ra một số nguyên: tổng chi phí nhỏ nhất để đi qua tất cả các đảo và quay lại đảo xuất phát.
Example
Test 1
Input
4
1 1
2 2
3 2
4 1Output
3note
- Khởi hành từ đảo \(1\).
- Chi phí thuê tàu ở mỗi đảo là tổng các \(p_i\):
\(1 + 2 + 2 + 1 = 6.\) - Nếu các đảo đã được sắp xếp theo độ cao, ta chỉ cần thêm phần chi phí tăng độ cao nếu chưa đủ tầm bay (khoảng vượt quá).
- Trong ví dụ này, tổng chi phí không cần thêm vì các tầm bay \(p_i\) đã đủ để đến các đảo cao hơn.
Bình luận