Transit#84

Transit (Розбір)

Позначимо через

f(m) = \sum_{i=1}^{N} \max(A_i - m,\; 0)

загальну кількість відвантажених обігрівачів за порогу . Країна не зазнає збитків, якщо f(m) \ge K, і треба знайти найбільше таке .

Головне спостереження: функція не зростає зі зростанням . Справді, збільшивши поріг на одиницю, кожен доданок або зменшиться на одиницю, або залишиться нулем. Отже, множина допустимих — це відрізок [0, m^*], і відповідь можна шукати двійковим пошуком.

Алгоритм: беремо межі пошуку від до \max A_i, на кожному кроці обчислюємо прямим підсумовуванням за і зсуваємо межі. Разом — \mathcal{O}(N \log \max A_i), що при N \le 10^6 цілком проходить.

Можна й швидше. Відсортувавши масив і побудувавши суфіксні суми, кожне обчислення робиться за \mathcal{O}(\log N): двійковим пошуком знаходимо перший елемент, більший за , і рахуємо (\text{сума таких елементів}) - m \cdot (\text{їх кількість}).

Стежте за типами: сума сягає 10^6 \cdot 10^9 = 10^{15}, тому лише 64-бітний тип. Умова гарантує, що відповідь існує, тому окремих випадків розглядати не треба.