How to minimize the average distance between pumps and cities?
Minimizing the average distance is equivalent to minimizing the sum of the distances, so let me work with that formulation of the problem. 

Hint #1: When $k = 1$, the pump should be located at the median of the positions of the cities. 

Hint #2: When $k &gt; 1$, you can use a dynamic programming approach. 
Let $f(i, j)$ be the optimal cost of serving cities $1,...,i$ with $j$ pumps. Your goal is to compute $f(n, k)$. Now observe that $$ f(n,k) = \min_{i=1,...,n} \left( \sum_{i': i &lt; i' \le n} d(\text{city}_{i'}, \text{pump}_k) + f(i,k-1) \right), $$
because if the rightmost pump (pump number $k$) serves cities $i+1$ through $n$, then the total cost is the sum of distances of those cities to pump $k$, plus the optimal cost of serving cities $1$ through $i$ with $k-1$ pumps. Here $\text{pump}_k$ is the position at the median of cities $i+1,...,n$.