BCCAR spoj PTIT – Đỗ xe tối ưu

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCCAR/

1. Đề bài BCCAR spoj PTIT

Khi mua sắm trên khu Long Street, Michael thường đỗ xe của mình ở một vị trí nào đó và đi bộ vào cửa hàng. Bạn hãy giúp Michael chọn một chỗ đỗ xe để khoảng cách phải đi bộ khi mua hàng là nhỏ nhất.

Long Street có thể coi như là một đường thẳng mà tất cả những điểm mua hàng là các điểm có tọa độ nguyên. Bạn sẽ phải trả phí cho mỗi lần đỗ xe ở một điểm đỗ, điểm đỗ là một điểm có tọa độ nguyên. Michael không muốn trả tiền đỗ xe nhiều hơn 1 lần và vì anh ta rất khỏe nên có thể mang tất cả các túi xách, hàng hóa mua được giữa các cửa hàng cần đi mà không có vấn đề gì. 

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 100 là số lượng bộ test. Mỗi bộ test gồm 2 dòng, dòng đầu tiên ghi số cửa hàng nmà Michael muốn qua mua hàng, 1 ≤ n ≤ 20 và dòng thứ hai ghi n số nguyên là các điểm này trên phố Long Street, 0 ≤ x_i ≤ 99. 

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng khoảng cách nhỏ nhất phải đi bộ với chỗ đỗ xe tối ưu.

2. Hướng dẫn BCCAR spoj PTIT

– Đề này viết hơi khó hiểu, nhưng có thể tạm giải thích như thế này:

– giả sử Michael dựng xe ở điểm A và anh ta sẽ đi hết tất cả các cửa hàng, ví dụ đầu tiên anh ta đứng ở A, sau đó anh ta đi đến các của hàng theo đường đến cửa hàng 1. (cửa hàng 2, 1 theo trong hình minh họa).

– Xong, anh ta phải đi đến cửa hàng 3 4 5, rồi quay về điểm đỗ xe.

– Dễ dàng nhận thấy anh ta đỗ xe ở đâu thì đường đi mà anh ta đi qua cũng như nhau, không thay đổi về khoảng cách.

Vậy nên ta chỉ cần tính khoảng cách của 2 cửa hàng xa nhất, ở đây tính theo tọa độ nên chỉ cần tìm min và max. Anh ta có 2 lượt đi, 1 là đi đến cửa hàng, 2 là đi về nên phải x2 khoảng cách.

Tổng quát: (Max(x[i])-Min(x[i]))*2 là kết quả bài toán.

3. code tham khảo BCCAR spoj PTIT