Банк#483

Банк (Розбір)

Автор, розробник, автор розбору: Тимур Деґтярь

Ключове спостереження (1) для цієї задачі полягає в тому, що кожна степінь числа може бути складена як сума менших степенів числа .

Оскільки порядок елементів масиву не має значення, ми можемо відсортувати його у спадному порядку і вважати, що відсортований.

Використовуючи спостереження (1), отримаємо спостереження (2). Нехай існує деякий масив довжини з властивістю b_i \geq b_{i+1} для всіх 1 \le i \le m-1, і S = S = 2^{b_1} + 2^{b_2} + 2^{b_3} + \dots + 2^{b_m}. Тоді кожне число з 2^{b_1}, 2^{b_1 + 1}, \dots, 2^{\lfloor \log_2(S) \rfloor} можна виразити як префіксну суму масиву .

Нехай S = 2^{a_1} + 2^{a_2} + 2^{a_3} + \dots + 2^{a_n} — загальна сума всіх витрат.

Позначимо через найменшу можливу найбільшу суму 2^{a_j} в одній категорії (тобто оптимальне значення, яке ми хочемо мінімізувати).

Якщо S < k \cdot 2^{a_1}, тоді Ans(a) = 2^{a_1}.

Оскільки принаймні одна категорія міститиме елемент 2^{a_1}, тому відповідь не може бути меншою за 2^{a_1}. З іншого боку, для кожної з інших категорій ми можемо поступово додавати елементи з масиву (у порядку спадання) доти, доки сума в цій категорії не стане рівною 2^{a_1} або ми не вичерпаємо всі елементи з . За спостереженням (2), це завжди можливо зробити, не перевищуючи 2^{a_1}.

Якщо S \geq k \cdot 2^{a_1}:

Розглянемо деяке оптимальне розбиття елементів масиву на категорій. Без втрати загальності будемо вважати, що перша категорія має найбільшу суму. Із кожної категорії візьмемо деяку підмножину елементів, яка в сумі дорівнює 2^{a_1} (або всі елементи з цієї категорії, якщо їхня сума менша за 2^{a_1}), і видалимо ці елементи з масиву . Позначимо отриманий після цього масив як a^{\prime}.

Очевидно, що перша категорія і надалі має найбільшу суму. Також очевидно, що Ans(a) = 2^{a_1} + Ans(a^{\prime}), оскільки інакше можна було б перерозподілити елементи між категоріями так, щоб ця рівність стала істинною в обидві сторони, що суперечить оптимальності.

Крім того, якщо для деякої категорії сума її елементів менша за 2^{a_1}, тоді a^{\prime} мусить бути порожнім: в іншому випадку ми могли б перекинути частину елементів з a^{\prime} у цю категорію і покращити (зменшити) максимальну суму, знову ж суперечачи оптимальності розбиття.

Позначимо через M = Ans(a), а через S = \sum_{i=1}^n 2^{a_i} — початкову загальну суму. Повторно застосовуючи перехід a := a^{\prime}, ми зрештою потрапимо в ситуацію, коли вже для деякого масиву a^{\prime} буде виконано 2^{a^{\prime}_1} \cdot k > \sum_i 2^{a^{\prime}_i}, тобто ми опинимось в випадку 1 для масиву a^{\prime} і тоді Ans(a^{\prime}) = 2^{a^{\prime}_1}. Оскільки на кожному кроці ми "знімаємо" з кожної категорії по сумі 2^{a_1}, загальна величина дорівнюватиме M = \frac{(S - \sum 2^{a^{\prime}_i})}{k} + 2^{a^{\prime}_1}, отже, оптимально мінімізувати найбільший елемент a^\prime, для чого достатньо використовувати префікс , щоб сформувати категорій зі сумами 2^{a_1}.

Таким чином, ми отримуємо жадібне рішення, яке виконується наступним чином:

Відсортуйте у спадному порядку, і поки він не порожній, якщо сума 2^{a_i} менша за k \cdot 2^{a_1}, призначте категорії таким чином, щоб жодна сума не перевищувала 2^{a_i} і завершіть. В іншому випадку, розділіть деякий префікс на категорій зі сумами рівно 2^{a_i}, видаліть цей префікс і продовжуйте.

Остаточна часова складність цього рішення, за правильної реалізації, становить \mathcal{O}(n \log n).