В супермаркете проводится акция «каждый четвертый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил на ленте товары группами по четыре товара, собираясь заплатить за каждую группу отдельным чеком. В каждой группе из четырех товаров самый дорогой он поместил на четвертое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной. Тогда покупатель разместил товары по-другому.

Вот как можно показать решение и понять, что именно покупатель мог сделать, чтобы максимизировать сумму к оплате. Ключевая идея - Программа на кассе не учитывает порядок на ленте. В каждом наборе из четырех товаров даёт бесплатным тот, чья цена минимальна в этом наборе (поскольку она размещается на позиции 4 и система сортирует цены так, чтобы была максимальная стоимость покупки для покупателя — т.е. бесплатен самый дешевый товар в группе). - Поэтому сумма к оплате равна сумме всех цен минус суммарная минимальная цена каждого набора из четырёх товаров. Задача сводится к тому, чтобы построить такие группы по четыре, чтобы сумма минимальных элементов этих групп была как можно меньше. Это достигается следующим образом: - Пусть всего n товаров, и n делится на 4 (g = n/4 групп). - Чтобы сумма минимальных элементов групп была минимальной, нужно выбрать g самых маленьких цен и сделать их минимумами в разных группах: каждая такая маленькая цена должна быть минимумом своей группы. - Это можно реализовать так: взять каждый из этих g самых маленьких товаров и объединить с ним три товара с максимально возможной ценой (чем дальше — тем лучше). Тогда в каждой группе минимум будет именно этой маленькой ценой, и никаких двух маленьких цен не окажется в одной группе (минимум каждой группы — отдельная малая цена). Итоговая формула - Обозначим prices — список цен всех товаров. - Пусть S — сумма всех цен. - Пусть k = n/4 — число групп. - Пусть minSum — сумма k самых маленьких цен (то есть сумма минимальных элементов групп при оптимальной раскладке). - Тогда максимальная сумма оплаты покупателя равна: S - minSum. - А сумма скидки (разница между полной суммой и оплаченной суммой) равна minSum. Пояснение на примере Допустим, 8 товаров (n = 8), цены: 1, 2, 3, 100, 101, 102, 103, 104. - g = n/4 = 2. Самые маленькие цены: 1 и 2. Пусть каждая из этих цен будет минимумом своей группы. - Группировка может быть такой: Группа 1: 1, 100, 103, 104 (минимум = 1) Группа 2: 2, 3, 101, 102 (минимум = 2) - Сумма минимальных = 1 + 2 = 3. - Сумма всех цен S = 1+2+3+100+101+102+103+104 = 516. - Максимальная оплата = S - minSum = 516 - 3 = 513. - Скидка = 3. Что это значит в общем - Независимо от конкретных цен, если количество товаров кратно четырём, максимальную сумму к оплате можно получить, сгруппировав минимума разных групп так, чтобы их сумма была минимальной: взять k самых маленьких цен и назначить их минимами в разных группах. - Затем на кассе каждый из этих минимумов окажется бесплатным, а остальные три товара в каждой группе будут платиться полностью. Алгоритм для вычисления (для задачи в программе) - Ввести список цен prices. - Посчитать S = сумма(prices). - Отсортировать prices по возрастанию. - Пусть k = n/4. - Вычислить minSum = сумма первых k элементов отсортированного списка. - Ответ (максимальная стоимость покупки) = S - minSum. Замечания - Предполагается, что количество товаров кратно 4. Если это не так, нужно уточнить правила акции для неполных групп. - Результат не зависит от исходного порядка товаров на ленте: покупатель может добиться максимума, если сгруппирует так, чтобы в каждой группе был один из k самых дешевых товаров и три самых дорогих других товара.