Where to Put the Mailboxes
Houses stand at given positions along a street. Place exactly k mailboxes anywhere on
the street. Each house walks to its nearest mailbox. Print the smallest possible total
walking distance.
houses 1 4 8 10 20, k = 3 -> 5
houses 2 3 5 12 18, k = 2 -> 9
## Each mailbox serves a contiguous block
Sort the houses. Then the houses served by one mailbox form a CONTIGUOUS run.
The reason: if house a and house c both use mailbox M and some house b between them
uses a different mailbox N, then N lies on one side of b, so it is at least as close to
whichever of a or c is on that side as M is. Reassigning that house to N never
increases the total, and repeating makes every assignment contiguous.
So the problem is a PARTITION of the sorted houses into k consecutive blocks, which is
what makes an interval-flavoured DP apply. Without sorting there is no such structure, so
the sort is part of the algorithm and not a convenience.
## The cost of one block is at the median
For a fixed block, the best mailbox position is a MEDIAN of that block, and the cost is the sum of distances to it.
The reason is worth knowing: moving the mailbox one step right changes the total by
(number of houses to the left) - (number of houses to the right), so the total decreases
while more houses lie to the right and increases after. The turning point is the median.
For an even-sized block, any position between the two middle houses gives the same total, so taking either middle house is correct.
## The two-part structure
cost[i][j] = the total distance for houses i..j served by one mailbox
dp[i][g] = the best total for the first i houses using g mailboxes
dp[i][g] = min over p of dp[p][g-1] + cost[p][i-1]
The interval table supplies the block costs and the partition table consumes them. Splitting the work that way keeps each half simple, and it is the same shape as problem 565.
## Boundaries
k equal to the number of houses answers 0: every house gets its own mailbox.
3 6 14 10 with k = 4 answers 0 and is the test.
k = 1 puts one mailbox at the median of everything. 7 4 6 1 with k = 1 answers 8, and
it is deliberately unsorted so a solution that skips the sort gets a wrong median.
1 2 with k = 1 answers 1 and with k = 2 answers 0.
## Cost
Time O(n^2 k) for the partition plus O(n^2) to build the block costs if each is computed
incrementally, or O(n^3) with the direct sum. Space O(n^2).