Дискотека#269

Дискотека (Розбір)

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

\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

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

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

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