В массиве prices — цены N товаров. Есть K одинаковых купонов. Один купон
уменьшает цену товара на X. На один товар можно наклеить сколько угодно
купонов: если применить t купонов к товару ценой a, он обойдётся в
max(a − t·X, 0) (ниже нуля цена не падает, сдачу не дают). Купоны можно не
использовать. Нужно купить все товары и вернуть минимально возможную
суммарную стоимость.
// MinCost возвращает минимальную суммарную стоимость всех товаров
// при оптимальном распределении k купонов номиналом x.
func MinCost(prices []int, k, x int) int
Пример
prices = [11, 6, 13, 8, 16], k = 5, x = 6 → 24
Ограничения
0 ≤ N, 0 ≤ k, 0 ≤ x, 0 ≤ prices[i].- Срез
prices менять нельзя.
- Ожидается не хуже O(N·log N).
Устно: почему «наклеиваем все купоны на самый дорогой товар» не всегда
оптимально? А «на разные товары поровну»? Чем купон, уводящий цену ниже нуля,
хуже остальных?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.