Дано n цілих чисел a 1 ,a 2 ,…,a n . Спочатку вони всі рівні нулю. Дано m операцій, кожен з яких описується двома числа k i та c i , які означають, що ви можете k i разів вибрати будь-який елемент з масиву a та замінити його значення на c i . Зверніть увагу, що елементи, які ви вибираєте, не обов'язково мають бути різними. Також ви не зобов'язані робити i-ту операцію рівно k i разів, ви можете виконати її будь-яку кількість разів, але не більше k i . Також ви можете не виконувати операцію взагалі. Всі m операцій ви маєте виконувати послідовно. Тобто, спочатку всі заміни першої операції, потім другої, і так далі. Знайдіть максимальну можливу суму масиву, що може вийти в кінці.
Answers & Comments
Відповідь:
Отже, маємо наступну задачу:
1. Даний масив `a[n]`, спочатку всі елементи дорівнюють 0
2. Дано m операцій у вигляді пар `(ki, ci)`
3. Кожна операція дозволяє `ki` разів замінити будь-який елемент масиву на `ci`
4. Операції потрібно виконувати послідовно
5. Потрібно знайти максимально можливу суму елементів масиву `a[n]` після виконання всіх операцій
Алгоритм розв'язання:
1. Пройтися по всіх операціях послідовно
2. Для кожної операції `(ki, ci)`:
1. Вибрати `ki` найменших елементів масиву `a[n]`
2. Замінити значення цих елементів на `ci`
3. Після виконання всіх операцій знайти суму елементів масиву `a[n]` - це і буде шуканий максимум
Отже, суть алгоритму - на кожному кроці вибирати найменші елементи і замінювати їх на поточне `ci`, що дозволить максимізувати підсумкову суму.