Что спрашивают
На бюджет S покупают товары P и T, каждый не более одного раза. Сначала нужно максимизировать общее количество, затем число товаров P, затем оставшиеся деньги.
Выведите число купленных P и остаток бюджета. Ввод: N, S, затем цена и тип каждого товара. N ≤ 100 000, S ≤ 10^9, цены ≤ 10 000. Хотя бы один товар купить можно.
Приём решения
Первым проходом найдём только максимальное общее количество k: отсортируем все цены и купим самый длинный помещающийся префикс. Его сумма минимальна среди любых наборов такой же длины, поэтому больше k товаров взять невозможно.
Теперь разделим цены по типам и построим префиксные суммы отдельно для P и T. При фиксированном числе p товаров P остаётся купить k - p товаров T. Минимальная стоимость такого набора равна prefixP[p] + prefixT[k - p]. Другой набор с тем же составом по типам стоить меньше не может.
Переберите p, для которых хватает товаров обоих типов. Если стоимость не больше S, сравните пару (p, S - cost) с лучшей. Так соблюдается порядок второго и третьего критериев. Максимальное k уже зафиксировано и в этом сравнении не меняется.
Нельзя просто предпочитать P при любой покупке: дорогой P может уменьшить общее количество. Время O(N log N), память O(N), перебор p после сортировок линейный.
Разбор на примере
Ввод
7 17 7 P 2 T 9 P 4 T 5 P 6 T 3 T
Вывод
2 0
| Количество P | Минимальная стоимость четырёх товаров | Решение |
|---|---|---|
| 0 | 2 + 3 + 4 + 6 = 15 | Помещается |
| 1 | 5 + 2 + 3 + 4 = 14 | Остаток 3 |
| 2 | 5 + 7 + 2 + 3 = 17 | Лучший состав |
| 3 | 5 + 7 + 9 + 2 = 23 | Не помещается |
Четыре самых дешёвых товара стоят 2 + 3 + 4 + 5 = 14, а пять стоят уже 20. Фиксируем четыре покупки. С одним P можно оставить 3 рубля; с двумя P покупаем 5, 7 и два T за 2 и 3, расходуя все 17. Два P важнее остатка, поэтому ответ 2 0.
Код на Python и C++
Нулевой элемент каждого массива префиксов равен нулю: так можно рассматривать покупки без P или без T. Равенство стоимости бюджету допустимо.
В C++ лучшая пара — pair<long long, long long>, и max сравнивает её в том же порядке.
import sys
def prefix(prices):
result = [0]
for price in sorted(prices):
result.append(result[-1] + price)
return result
def solve(budget, items):
count = spent = 0
for price in sorted(price for price, kind in items):
if spent + price > budget:
break
spent += price
count += 1
p = prefix(price for price, kind in items if kind == 'P')
t = prefix(price for price, kind in items if kind == 'T')
best = (-1, -1)
low = max(0, count - (len(t) - 1))
high = min(count, len(p) - 1)
for amount in range(low, high + 1):
cost = p[amount] + t[count - amount]
if cost <= budget:
best = max(best, (amount, budget - cost))
return best
if __name__ == '__main__':
stream = sys.stdin
n, budget = map(int, stream.readline().split())
items = []
for _ in range(n):
price, kind = stream.readline().split()
items.append((int(price), kind))
print(*solve(budget, items))
<algorithm>
<iostream>
<utility>
<vector>
using namespace std;
// prefix[i] — сумма i самых дешёвых цен.
vector<long long> prefix(vector<long long> prices) {
sort(prices.begin(), prices.end());
vector<long long> result = {0};
for (long long price : prices)
result.push_back(result.back() + price);
return result;
}
int main() {
int n;
long long budget;
cin >> n >> budget;
vector<long long> all, p_prices, t_prices;
for (int i = 0; i < n; i++) {
long long price;
char kind;
cin >> price >> kind;
all.push_back(price);
(kind == 'P' ? p_prices : t_prices).push_back(price);
}
sort(all.begin(), all.end());
int count = 0;
long long spent = 0;
for (long long price : all) {
if (spent + price > budget)
break;
spent += price;
count += 1;
}
vector<long long> p = prefix(p_prices), t = prefix(t_prices);
pair<long long, long long> best = {-1, -1};
int low = max(0, count - ((int)t.size() - 1));
int high = min(count, (int)p.size() - 1);
for (int amount = low; amount <= high; amount++) {
long long cost = p[amount] + t[count - amount];
if (cost <= budget)
best = max(best, {(long long)amount, budget - cost});
}
cout << best.first << ' ' << best.second << endl;
}
Типичные ошибки
- В первую очередь покупать P
Первый критерий — общее число товаров. Нельзя жертвовать одной покупкой ради предпочтительного типа.
- Оставить исходный дешёвый набор
Он определяет только k. Среди других наборов из k товаров может оказаться больше P.
- Сравнить остаток раньше типа
Больший остаток улучшает ответ лишь при равном количестве P. Сравнивайте пару в указанном порядке.