http://tonancos.com/3nHS
Tags: binary search, greedy
Solution:
First, we binary search the time it's going to take the person who takes the most time to get to their floor. Inside the binary search, we choose which floor to put the stops on greedily. The greedy part is wanting to put the stop as far from the beginning as we can so that it still covers floors it would take too long to walk to. I'm not so sure on why because it could just be intuitive, or that the less stops we make the better, so putting it further down lowers the amount of stops we need to use.
Example:
Input = 3 3 5 6
The answer to this is 32 (it takes 32 minutes) 2 4 6 (put the stops on floors 4 and 6). To get this, let's say in our binary search mid is 32. First we check if we can walk to any of the floors during this time, but we can't (if there was 2 in the input, we could walk to 2 since 32 is over 20). Then, let's say start = 3, we iterate floors to put the next stop on (3 (start), 4 (start+1), 5 (start+2)...) until the floor we iterate over is too far away from 3 (start) to walk to. This floor in this example is 5, because if we stop at 5, it would take 4*4+20*2 minutes to get from 5 to 3. Since we know 5 is too big, 4 must be the floor to put the stop on. To get from 4 to 3, it takes 32 minutes. After we put the floor on 4, we go on to see which floors above floor 4 can be reached in at most 32 minutes. 5 can be reached from 4 in 32 minutes, so we skip over 5 and don't put a stop there. After we reach the point where a floor can't be reached by 4, we take that floor and assign start to it, and repeat the part before this. You can just put a stop at the last floor (in this case 6) because it doesn't affect the time.
My code: http://tonancos.com/3nIN
No comments:
Post a Comment