Fountain Spots
Time limit1sMemory limit256 MB
Place K houses at distinct integer positions on a line so that the total distance from each house to its nearest fountain spot is minimized, given N fountain positions.
Problem
On a straight line there are N fountain spots, and we want to build K houses. Every fountain spot and every house sits at an integer position. All N fountain spots and all K houses occupy distinct positions on the line. In other words, each position holds either a fountain spot, a house, or nothing at all.
When building the K houses, we want to place them as close to the fountain spots as possible so that the sum of unhappiness over all K houses is minimized. The unhappiness of a particular house is defined as the distance to the nearest fountain spot. For example, if a house is at 1 and the nearest fountain spot to it is at -5, the unhappiness of this house is 6.
Consider building houses so that the sum of unhappiness over all houses is minimized when N=2 and K=5. Suppose two fountain spots are at positions 0 and 3, as in the figure below.
If we place 5 houses as follows, the sum of unhappiness is 2+1+1+1+1=6, which is minimal. There can be many ways to build the houses, but no way makes the sum of unhappiness smaller than 6.
Input
The first line gives the positive integers N and K, separated by a space. (1 ≤ N, K ≤ 100,000) The second line gives the positions of the N fountain spots as integers separated by spaces. (-100,000,000 ≤ position of a fountain spot ≤ 100,000,000) All N fountain spot positions are distinct.
Output
Print the minimum sum of unhappiness over all houses on the first line.