GeeksforGeeks

Ми використовуємо файли cookie, щоб забезпечити найкращий досвід перегляду веб-сайту. Використовуючи наш веб-сайт, ви підтверджуєте, що прочитали та розумієте нашу Політику використання файлів cookie та Політику конфіденційності

У кондитерському магазині доступно N різних типів цукерок, і вказані ціни на всі N різних типів цукерок. Також є приваблива пропозиція цукеркового магазину. Ми можемо придбати одну цукерку в магазині та безкоштовно отримати не більше K інших цукерок (усі різні типи).

Знайдіть мінімальну суму грошей, яку ми повинні витратити, щоб придбати всі N різних цукерок.
Знайдіть максимальну суму грошей, яку ми повинні витратити, щоб придбати всі N різних цукерок.

В обох випадках ми повинні скористатися пропозицією і отримати максимально можливі цукерки. Якщо доступно k або більше цукерок, ми повинні взяти k цукерок за кожну покупку цукерок. Якщо доступно менше k цукерок, ми повинні взяти всі цукерки для придбання цукерок.

Приклади:

Важливо зазначити, що ми повинні скористатися пропозицією та отримати максимум цукерок за кожну покупку цукерок. Отже, якщо ми хочемо мінімізувати гроші, ми повинні купувати цукерки з мінімальними витратами і безкоштовно отримувати цукерки з максимальними витратами. Щоб максимізувати гроші, ми повинні зробити зворотне. Нижче наведений алгоритм, заснований на цьому.

Нижче наведено ілюстрацію вищезазначеного підходу:

Нижче наведено реалізацію вищезазначеного підходу: