Філателія#355

Філателія (Розбір)

Марки коштують 1, 2, \ldots, N доларів, і треба набрати рівно , узявши якнайменше марок.

Спочатку перевіримо здійсненність: максимально можлива сума — це 1 + 2 + \ldots + N = \frac{N(N+1)}{2}. Якщо більше за неї, набрати потрібну суму неможливо.

Далі працює проста жадібність: щоразу беремо найдорожчу марку, яку ще можна взяти, не перевищивши залишок. Формально, поки залишок додатний:

  • якщо M > N, беремо марку номіналу , зменшуємо на і переходимо до N - 1;

  • інакше беремо марку номіналу рівно і завершуємо.

Чому це мінімально? Якщо ми взяли марок, їхня сума не перевищує суми найдорожчих, тобто N + (N-1) + \ldots + (N-t+1). Жадібний алгоритм саме й бере найдорожчі, тому він досягає потрібної суми за найменшу можливу кількість кроків. Другий випадок гарантує, що ми потрапляємо точно в ціль: залишок M \le N сам є номіналом ще не використаної марки.

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

Кількість кроків не перевищує \mathcal{O}(\sqrt{M}), бо сума перших взятих марок зростає квадратично. Суму \frac{N(N+1)}{2} рахуйте у 64-бітному типі.