Editorial for DMOPC '18 Contest 2 P2 - Booster Cushions

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.

Author: r3mark

The tallest people should always be at the front. Additionally, it is always better to fill up a column rather than start a new one. Based on this, it is simple to implement an optimal seating. Calculate the number of columns required ( $\left\lceil \frac{K}{M} \right\rceil$ ~\left\lceil \frac{K}{M} \right\rceil~) and place the tallest people at the front of each column. Then, fill up the columns with the rest of the people.

Time Complexity: $\mathcal{O}(K)$ ~\mathcal{O}(K)~

Comments

There are no comments at the moment.