There are n
cities [1, 2, 3, .... n] and k
available pumps. These pumps can be installed in k
cities. The cities are all in a straight line.
How do I need to install these so that the average distance between the cities and the nearest pumps is minimized?
What I am thinking is that dividing is this:
Suppose there are 6 cities [C1, C2, C3, C4, C5, C6]
and 3 pumps [P1, P2, P3]
.
I divide the array of cities equally -> [C1, C2] , [C2, C3] ..
and then each block gets one pump.
Then again break that [C1,C2]
and let C2
have the pump. Same way C4
and C6
.
So basically recursively calling and assigning the city a pump. Is this the right way to approach this problem?