The formal statement of the problem is follows: given N points on a straight line, and the sequence n1, n2, n3... is non-decreasing. Arrange M points so that the sum of the distances from the nearest points ni, n(i+1)... to the point mi would be minimal for i = 1...M.
Informal interpretation of the problem: arrange M gas stations on the road so that N people living along the road spend as little time as possible getting to the gas station. For a single gas station, the condition is simple: the number of people to the right and left of the gas station must be equal.
M<=N
For a larger number of gas stations, the task becomes more complicated. I gave an example of placing 3 gas stations among 10 dots. Each of them creates a certain segment, and on this segment there are the same number of people to the right and to the left of the gas station.
However, this is not the optimal solution. My assumption: for optimality, an additional condition is required: on the right and on the left there must be the same number of points for which this gas station is the closest. An example of such an arrangement is shown in the figure below, and indeed, the sum of the distances for such a situation is less.
The problem is that I do not understand how to check at the stage of arranging gas stations which point will be the closest. This can be seen in the first picture: we place the dots so that there are the same number of people on each side, but after the placement it turns out that the gas station nearest to them is not the one we expected.