Козак Вус та міньйони#139

Козак Вус та міньйони (Editorial)

Ціна загону — це сила лідера плюс витривалості решти учасників. Отже, у загоні розміру рівно один міньйон дає свою , а інші k-1 — свої .

Звідси стратегія: щоб зменшити ціну, у загін вигідно брати міньйонів з найменшими . Відсортуємо всіх за за зростанням і побудуємо префіксні суми \mathrm{pref}[t] = b_1 + \ldots + b_t.

Тепер для фіксованого можливі рівно два випадки.

Випадок 1: лідер — не з k-1 найменших за витривалістю. Тоді решту загону складають перші k-1 міньйонів відсортованого масиву, а лідером стає будь-хто з решти. Вигідно взяти того, у кого найменша сила:

\mathrm{pref}[k-1] + \min_{i \ge k} a_i.

Мінімум справа — це суфіксний мінімум масиву , який рахується одним проходом.

Випадок 2: лідер — один із перших за витривалістю. Тоді загін складається саме з перших міньйонів, і один з них — лідер. Якщо лідер має індекс i \le k, то ціна дорівнює

a_i + (\mathrm{pref}[k] - b_i) = \mathrm{pref}[k] + (a_i - b_i).

Отже, вигідно взяти лідером того, у кого найменша різниця a_i - b_i, а це префіксний мінімум масиву a_i - b_i.

Відповідь — мінімум із двох випадків. Обидва допоміжні масиви (суфіксний мінімум і префіксний мінімум a - b) обчислюються заздалегідь, тому кожне знаходиться за .

Загальна складність — \mathcal{O}(n \log n) через сортування. Суми сягають 2 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}, тому обов'язково 64-бітний тип.