Кристали#53

Кристали (Розбір)

Давайте ми спочатку будемо використовувати лише звичайні запуски, а потім лише посилені запуски.

Нехай ми використали c_1 звичайних запусків першого кристалу, c_2 другого, і так далі. Нехай c_i > 0, c_j > 0, i \neq j, a_i < a_j, тоді нам немає сенсу використовувати -ий кристал у звичайному режимі, замість нього ми могли б використати кристал та отримати більше. Отже, є сенс використовувати лише один кристал у звичайному режимі - кристал з максимальним a_i. Нехай a_m — максимальний a_i.

Але як зрозуміти, скільки разів нам потрібно його використовувати? У нас можуть бути кристали, у яких b_i > a_m. Тоді є сенс використовувати їх.

Відсортуємо b_i за спаданням. Видалимо усі b_i, які менші за a_m. Будемо брати b_i по черзі (у порядку спадання) доти, доки ми не отримаємо сумарно принаймні . Якщо ж ми всі видалили, але цього недостатньо, то будемо тепер використовувати a_m стільки разів, скільки потрібно. Нехай — це та потрібна кількість використань a_m, щоб отримати .

Отже, ми тепер можемо спочатку використати кристал (той, у якого максимальне a_i) разів ( може бути ) у звичайному режимі, після цього використовувати кристали з максимальними b_i у посиленому режимі.