Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
The first main insight to make is that each student should either walk all the way to their destination, or take the bus all the way. For example, the only reason a student might want to take the bus partially and then walk is to make space for another student getting on at that stop, but at that point those 
~2~ students might as well have switched places from the start, so it can't be any more beneficial.
The second main insight to make is that students with further destinations are more likely to want to take the bus than students with closer ones. In other words, if only 
~1~ of ~2~ students is going to take the bus, then it should be the one with the further destination, as the time saved by taking the bus will be multiplied over more stops.
The above pair of insights suggest the following greedy algorithm: Sort the students' destinations 
~D_{1 \dots M}~, and process them in non-increasing order (the furthest ones first). For each student in that order, greedily have them either walk all the way or take the bus all the way, whichever is faster. Students assigned to taking buses may increase the bus travel times for later students, which is why it's important to process the students with the furthest destinations first, so that they get priority for filling the buses.
As for the details of computing the students' travel times, we can maintain 
~3~ values during the greedy process: The sum 
~s~ of travel times so far (initially 
~0~), the time 
~t~ at which the current bus will arrive at stop ~1~ (initially ~0~), and the number of remaining spots 
~r~ on the current bus (initially 
~C~). The travel time if the student 
~i~ walks is therefore 
~(D_i-1) \times W~, while the travel time if they take the bus is 
~t+(D_i-1) \times B~. ~s~ should be increased by the smaller of these ~2~ values. Then, if we've decided that this student should take the bus, we need to record that by decrementing ~r~. If ~r~ becomes ~0~, then future students will need to take the next bus, meaning that we should increase ~t~ by 
~P~ and reset ~r~ to ~C~. After processing all 
~M~ students in this fashion, ~s~ will contain the final answer.
The time complexity of this algorithm is 
~\mathcal O(M \log M)~, which is the time required to optimally sort the values ~D_{1 \dots M}~.
Comments