JOI 2023 - Bitaro's Travel
Xem PDFThành phố JOI có một con đường rất dài, có thể xem như trục số thực. Mỗi vị trí trên đường được biểu diễn bằng một tọa độ thực. Dọc con đường có \(N\) điểm tham quan, đánh số từ \(1\) đến \(N\) theo thứ tự tọa độ tăng dần. Điểm tham quan thứ \(i\) (\(1\le i\le N\)) có tọa độ \(X_i\).
Bitaro sẽ ghé thăm tất cả các điểm tham quan. Vì phương châm sống của cậu là "tham lam", cậu lặp lại quy trình sau cho đến khi đã thăm hết:
- Gọi \(x\) là tọa độ hiện tại của Bitaro. Trong số các điểm chưa ghé thăm, chọn điểm \(i\) có khoảng cách \(|x-X_i|\) nhỏ nhất. Bitaro di chuyển đến tọa độ của điểm \(i\) và ghé thăm điểm đó. Nếu có nhiều điểm cùng đạt khoảng cách nhỏ nhất, cậu chọn điểm có tọa độ nhỏ nhất. Ở đây, \(|t|\) là giá trị tuyệt đối của \(t\).
Qua nhiều năm kinh nghiệm, Bitaro biết rằng quy trình này có thể khiến tổng quãng đường di chuyển dài hơn dự kiến. Tổng quãng đường phụ thuộc vào tọa độ xuất phát. Vì vậy, với mỗi tọa độ xuất phát trong \(Q\) lựa chọn \(S_1,S_2,\ldots,S_Q\), cậu muốn biết tổng quãng đường phải đi cho đến khi đã ghé thăm tất cả các điểm.
Cho thông tin về các điểm tham quan và các tọa độ xuất phát, hãy tính tổng quãng đường di chuyển của Bitaro với từng lựa chọn.
Dữ liệu vào
Đọc từ đầu vào chuẩn theo định dạng:
N
X_1 X_2 ... X_N
Q
S_1
S_2
...
S_Q
Dữ liệu ra
Xuất \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1\le j\le Q\)) chứa tổng quãng đường Bitaro di chuyển nếu xuất phát tại tọa độ \(S_j\).
Ràng buộc
- \(1\le N\le200\,000\).
- \(1\le Q\le200\,000\).
- \(0\le X_i\le10^9\) với \(1\le i\le N\).
- \(X_i<X_{i+1}\) với \(1\le i\le N-1\).
- \(0\le S_j\le10^9\) với \(1\le j\le Q\).
- Tất cả giá trị đầu vào đều là số nguyên.
Phân nhóm
Mọi nhóm đều tuân theo các ràng buộc chung ở trên.
- \(5\) điểm: \(Q=1\), \(N\le2\,000\).
- \(10\) điểm: \(Q=1\).
- \(30\) điểm: \(X_{i+1}-X_i\le100\) với mọi \(1\le i\le N-1\).
- \(55\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
5
0 5 6 7 9
1
7Output
15Giải thích
Khi xuất phát tại tọa độ \(7\), Bitaro ghé thăm các điểm như sau:
- Các điểm chưa thăm là \(1,2,3,4,5\), có khoảng cách đến vị trí hiện tại lần lượt là \(7,2,1,0,2\). Điểm \(4\) gần nhất, nên Bitaro ở nguyên tọa độ \(7\) và ghé thăm điểm \(4\).
- Các điểm chưa thăm là \(1,2,3,5\), có khoảng cách lần lượt là \(7,2,1,2\). Điểm \(3\) gần nhất, nên cậu di chuyển từ tọa độ \(7\) đến tọa độ \(6\) và ghé thăm điểm \(3\).
- Các điểm chưa thăm là \(1,2,5\), có khoảng cách lần lượt là \(6,1,3\). Điểm \(2\) gần nhất, nên cậu di chuyển từ tọa độ \(6\) đến tọa độ \(5\) và ghé thăm điểm \(2\).
- Các điểm chưa thăm là \(1,5\), có khoảng cách lần lượt là \(5,4\). Điểm \(5\) gần nhất, nên cậu di chuyển từ tọa độ \(5\) đến tọa độ \(9\) và ghé thăm điểm \(5\).
- Chỉ còn điểm \(1\) chưa thăm. Cậu di chuyển từ tọa độ \(9\) đến tọa độ \(0\) và ghé thăm điểm \(1\).
Tổng quãng đường di chuyển là \(15\), nên xuất 15. Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.
Ví dụ 2
Input
10
1 2 3 4 5 6 7 8 9 10
10
1
2
3
4
5
6
7
8
9
10Output
9
10
11
12
13
14
15
16
17
9Giải thích
Ví dụ này thỏa mãn ràng buộc của các nhóm \(3,4\).
Nguồn
JOI 2022/2023 Spring Training, Contest 4, bài Bitaro's Travel, tác giả 米田寛峻 và 米田優峻.
Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2023 - Tuyển chọn mùa xuân - Ngày 4 (22 Tháng ba, 2023)
Bình luận