Навчимось перевіряти, чи можна вибрати набір пісень, що в нього відношення суми рейтингу до суми тривалості більше або дорівнює .
Таким чином, завжди оптимально брати пісень, які мають найбільше значення різниці r_i - t_i \cdot x.
Зробимо бінарний пошук по відповіді, будемо проходитись по масиву, сортувати й шукати суму перших . Якщо сума більше ніж , то можна отримати відповідь рівну , інакше ні.
Загальна асимптотика — \mathcal{O}(N \log A \log N).