Editorial for ICPC PACNW 2016 I - Postman
Submitting an official solution before solving the problem yourself is a bannable offence.
Postman is a simulation problem, but one with a few traps.
The basic approach is to simply deliver as many letters as possible to the furthest houses first; you must make at least that many trips at that distance, so this is optimal. If you instead try to deliver to the closest houses first, you may end up with a suboptimal solution; consider the case:
House | Distance | Letters |
---|---|---|
with a postman capacity of
If instead he takes a round trip to house
The problem is the number of letters and the distances can be large (although the count of houses is small). If you simulate each individual trip, you will run out of time, because the total number of letters could be as high as
The second trap is a common one—the result may not fit in a 32-bit int so you need to use doubles or 64-bit ints.
Comments