Let the optimal parking spot be x. The position of the stores are given as a1,a2,a3,…,an. It is easy to see that,

min(a1,a2,a3,…,an)≤x≤max(a1,a2,a3,…,an)min(a_1, a_2, a_3,\ldots,a_n) \leq x \leq max(a_1, a_2, a_3,\ldots,a_n)

Now let’s sort the store positions for ease of calculation. Sorting, however, won’t change the output. Because from the optimal spot, we have to visit all the store positions anyway. After sorting, the store positions become,

a1′≤a2′≤…≤an′ a_1^\prime \leq a_2^\prime \leq \ldots \leq a_n^\prime

Where, a1′=min(a1,a2,a3,…,an) and an′=max(a1,a2,a3,…,an).

Starting from x, the cost of walking then becomes,

(x−a1′)+(a2′−a1′)+(a3′−a2′)+…+(an′−an−1′)+(an′−x) (\cancel{x} - a_1^\prime) + (\cancel{a_2^\prime} - a_1^\prime) + (\cancel{a_3^\prime} - \cancel{a_2^\prime}) + \ldots + (a_n^\prime - \cancel{a_{n-1}^\prime}) + (a_n^\prime - \cancel{x}) =2∗(an′−a1′) = 2 * (a_n^\prime - a_1^\prime)

Let’s look at an example. Suppose 4 store locations are 24,13,89,37. Now assuming x as the optimal parking spot, our calculation becomes,

(x−13)+(24−13)+(37−24)+(89−37)+(89−x) (x - 13) + (24 - 13) + (37 - 24) + (89 - 37) + (89 - x) =2∗(89−13) = 2 * (89 - 13) =152 = 152

Here’s the solution in C++:

#include <iostream>
#include <algorithm>
int main(int argc, char const *argv[])
{
int T; std::cin >> T;
while(T--){
int n; std::cin >> n;
int mx = 0, mn = 100;
for(int i = 0 ; i < n ; ++i){
int x; std::cin >> x;
mx = std::max(mx, x);
mn = std::min(mn, x);
}
std::cout << 2 * (mx - mn) << '\n';
}
return 0;
}
view raw uva-11364.cpp hosted with ❤ by GitHub