Editorial for An Animal Contest 3 P3 - Monkey Market - Olympiads Online Judge

Editorial for An Animal Contest 3 P3 - Monkey Market

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: WilliamWu277

We notice that it is always optimal to buy at the smallest $\lfloor \frac N 2 \rfloor$ ~\lfloor \frac N 2 \rfloor~ prices and sell at the largest $\lfloor \frac N 2 \rfloor$ ~\lfloor \frac N 2 \rfloor~ prices. We sort the $N$ ~N~ numbers and place them in an alternating fashion like S L S L, where S denotes one of the smallest $\lfloor \frac N 2 \rfloor$ ~\lfloor \frac N 2 \rfloor~ prices and vice versa for L. Since order does not matter for multiplication and division, it suffices to place the numbers in any order that satisfies the alternating fashion.

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

Comments

There are no comments at the moment.