Postal Delivery
This problem asks us what is the minimum distance needed to travel to deliver various amounts of letters to various locations on the x axis when we are limited in carrying capacity.
It is easy to see that a greedy solution is optimal, as there is no downside to carrying more letters than one needs for a given trip. Fill up, and carry to the most negative location. Any extra space is allocated to the next most negative location and vice versa. Also note that there is never a situation where it is beneficial to carry letters across the origin, so the two halves can be solved independently. This makes the problem simpler to code as we can simply flip all the negatives and solve the problem twice, rather than writing the code to work for both positive and negative.
If coded naively, one may. The naive solution be to:
- fill up truck
- empty at furthest location which needs letters still
This becomes an issue when the number of letters needed is large. Consider 1000 addresses, each requiring 800 letters, with a capacity of 1. That requires 800,000 evaluations. Actually, that's plenty fast! The runtime, ultimately, is O(N*t)
But we can do better than that.
If we have a small capacity and large number of letters, we can "simulate" every visit to that location in one go. Simply divide the letters required by the capacity (integer division, of course), and that's the number of trips there. Add the distance for all those trips to the total, and subtract the letters delivered off those required. If there is a remainder, we still have to eat the total distance, but the extra we can subtract off the next closest house, and if there is any more required there, we can do the division trick again.
This optimization, while not required here, does come up. It reduces the complexity to O(N) since we finish each house in at most 2 steps: a division step, and a "finish the extra" step.