Что спрашивают
Покупатель разбивает N товаров на чеки по девять. Оставшиеся меньше девяти оплачиваются полностью. Сначала он надеется сделать бесплатным самый дорогой товар каждого чека, но касса бесплатно отдаёт самый дешёвый.
Для обоих правил товары можно перегруппировать. Найдите минимальную планируемую и минимальную фактическую сумму. N ≤ 10 000, цены от 1 до 10 000.
Приём решения
В обоих случаях выгодно максимизировать скидку. Чеков со скидкой будет g = N // 9. Если бесплатен самый дорогой, бесплатно можно получить g самых дорогих товаров: к каждому достаточно добавить восемь остальных. Планируемая оплата — общая сумма минус сумма g максимумов.
Если бесплатен самый дешёвый, к каждому бесплатному нужны восемь товаров не дешевле него. Отсортируйте цены по убыванию и разделите на последовательные группы по девять. Бесплатными станут элементы с индексами 8, 17, 26 и далее; хвост оплачивается полностью.
Почему это оптимально? Если расположить минимумы чеков по убыванию, для первых j минимумов нужны 9j товаров не дешевле j-го минимума. Значит, j-й минимум не может быть больше элемента на позиции 9j в общей сортировке. Последовательные группы достигают этой границы для всех j одновременно.
Время O(N log N), память O(N). Не надо моделировать порядок выкладывания внутри чека: фактическая программа его не учитывает.
Разбор на примере
Ввод
19 19 3 17 5 15 7 13 9 11 1 18 2 16 4 14 6 12 8 10
Вывод
153 177
| Правило | Бесплатные товары | Оплата |
|---|---|---|
| План: максимум каждого чека | 19 и 18 | 190 − 37 = 153 |
| Касса: минимум каждого чека | 11 и 2 | 190 − 13 = 177 |
| Хвост фактической группировки | Нет скидки для цены 1 | Уже включён в 177 |
Цены — все числа от 1 до 19, общая сумма 190. Два бесплатных максимума 19 и 18 дают планируемую оплату 153. Фактически выгодны группы 19–11 и 10–2: бесплатно уйдут 11 и 2. Товар за 1 оплачивается отдельно, итог 190 - 13 = 177.
Код на Python и C++
При N < 9 оба среза пусты и скидка равна нулю. Нумерация в Python с нуля: девятый элемент имеет индекс 8.
В C++ срезов нет. Скидку по группам считает цикл по первым groups ценам, сумму на кассе — цикл for (i = 8; i < n; i += 9). Индексы в C++ тоже начинаются с нуля.
import sys
def solve(prices):
prices = sorted(prices, reverse=True)
total = sum(prices)
groups = len(prices) // 9
planned = total - sum(prices[:groups])
actual = total - sum(prices[8::9])
return planned, actual
if __name__ == '__main__':
n, *prices = map(int, sys.stdin.buffer.read().split())
print(*solve(prices))
<algorithm>
<functional>
<iostream>
<vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> prices(n);
long long total = 0;
for (long long& price : prices) {
cin >> price;
total += price;
}
sort(prices.begin(), prices.end(), greater<long long>());
int groups = n / 9;
long long planned = total, actual = total;
for (int i = 0; i < groups; i++)
planned -= prices[i];
for (int i = 8; i < n; i += 9)
actual -= prices[i];
cout << planned << ' ' << actual << endl;
}
Типичные ошибки
- Взять самые дешёвые товары бесплатно
Группы можно менять. Девять дорогих вместе дают большую скидку, чем смешивание дорогих с дешёвыми.
- Посчитать один общий чек
Условие разрешает отдельный чек на каждую группу из девяти. Именно группировка определяет скидку.
- Выдать скидку за неполную группу
Хвост короче девяти оплачивается целиком. Срез 8::9 не содержит элемент из такого хвоста.