Дискотека

Навчимось перевіряти, чи можна вибрати набір пісень, що в нього відношення суми рейтингу до суми тривалості більше або дорівнює $$$x$$$.

$$$$$$\displaystyle \frac{\sum_{i \in X} r_i}{\sum_{i \in X} t_i} \ge x$$$$$$ $$$$$$\displaystyle \sum_{i \in X} r_i \ge x \cdot \sum_{i \in X} t_i$$$$$$ $$$$$$\displaystyle \sum_{i \in X} (r_i-t_i \cdot x) \ge 0$$$$$$

Таким чином, завжди оптимально брати $$$k$$$ пісень, які мають найбільше значення різниці $$$r_i - t_i \cdot x$$$.

Зробимо бінарний пошук по відповіді, будемо проходитись по масиву, сортувати й шукати суму перших $$$k$$$. Якщо сума більше ніж $$$0$$$, то можна отримати відповідь рівну $$$x$$$, інакше ні.

Загальна асимптотика — $$$\mathcal{O}(N \log A \log N)$$$.