Что спрашивают
Для каждого из N участков покупают отдельный снегоуборщик. Мощность не ниже требования, цена минимальная, при равной цене мощность максимальная. Экземпляров каждой модели неограниченно.
Найдите общую стоимость и максимальную мощность купленного. Ввод: N, K, N требований, затем K пар «мощность, цена». N ≤ 100 000, K < 100 000, мощности ≤ 1000, цены ≤ 100 000. Для каждого требования модель найдётся.
Приём решения
Нельзя ограничиваться моделью с ближайшей достаточной мощностью: более мощная может стоить дешевле. Для требования q подходят все мощности от q до 1000 — суффикс диапазона.
В массив best сначала поместим лучший вариант каждой точной мощности. Пару сравниваем как (цена, -мощность): минимум даёт минимальную цену и максимальную мощность при её равенстве. Затем идём от 1000 к 1 и присваиваем best[q] = min(best[q], best[q + 1]).
После такого прохода best[q] содержит лучший вариант среди всех мощностей не меньше q. Доказательство по убыванию q: подходящие модели либо имеют точную мощность q, либо уже представлены в best[q + 1]. Для каждого участка теперь достаточно одного обращения к массиву.
Модели не удаляются после покупки: запас неограничен. Время O(N + K + 1000), дополнительная память O(1000), помимо сохранённого ввода.
Разбор на примере
Ввод
3 5 4 8 10 4 11 6 7 9 7 8 9 12 13
Вывод
27 12
| Требование | Выбранная модель | Причина |
|---|---|---|
| 4 | 9 за 7 | Дешевле точного совпадения; мощнее при равной цене |
| 8 | 9 за 7 | Дешевле модели 8 за 9 |
| 10 | 12 за 13 | Остальные слишком слабы |
Требованию 4 подходит любая модель, в том числе точная 4 за 11. Дешевле всех стоят 6 и 9 — по 7; при равной цене выбираем мощность 9. Для требования 8 тоже выгоднее 9 за 7, чем 8 за 9. Для требования 10 остаётся модель 12 за 13. Итоговая стоимость 7 + 7 + 13 = 27, наибольшая купленная мощность 12.
Код на Python и C++
Цена 100001 используется как заведомо недопустимо большая. Гарантия подходящей модели означает, что это значение не попадёт в стоимость покупки.
В C++ пара (цена, -мощность) — pair<int, int>, и min сравнивает её так же. Общая стоимость может быть больше 231, поэтому она хранится в long long.
import sys
def solve(needs, models):
best = [(100001, 0)] * 1002
for power, cost in models:
best[power] = min(best[power], (cost, -power))
for power in range(1000, 0, -1):
best[power] = min(best[power], best[power + 1])
total = maximum = 0
for need in needs:
cost, negative_power = best[need]
total += cost
maximum = max(maximum, -negative_power)
return total, maximum
if __name__ == '__main__':
data = list(map(int, sys.stdin.buffer.read().split()))
n, k = data[:2]
needs = data[2:2 + n]
models = list(zip(data[2 + n::2], data[3 + n::2]))
print(*solve(needs, models))
<algorithm>
<iostream>
<utility>
<vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> needs(n);
for (int& need : needs)
cin >> need;
// best[q] — пара (цена, -мощность) лучшей модели мощностью не меньше q.
vector<pair<int, int>> best(1002, {100001, 0});
for (int i = 0; i < k; i++) {
int power, cost;
cin >> power >> cost;
best[power] = min(best[power], {cost, -power});
}
for (int power = 1000; power > 0; power--)
best[power] = min(best[power], best[power + 1]);
long long total = 0;
int maximum = 0;
for (int need : needs) {
auto [cost, negative_power] = best[need];
total += cost;
maximum = max(maximum, -negative_power);
}
cout << total << ' ' << maximum << endl;
}
Типичные ошибки
- Выбрать ближайшую мощность
Минимизируется цена, а не избыток мощности. Дальняя по мощности модель может быть выгоднее.
- Хранить пару цена, мощность для min
При равной цене min выбрал бы меньшую мощность. Минус перед мощностью задаёт нужный второй критерий.
- Убрать купленную модель
Количество экземпляров неограниченно. Одну лучшую модель можно купить для многих участков.