Что спрашивают

На бюджет 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Минимальная стоимость четырёх товаровРешение
02 + 3 + 4 + 6 = 15Помещается
15 + 2 + 3 + 4 = 14Остаток 3
25 + 7 + 2 + 3 = 17Лучший состав
35 + 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))
#include <algorithm>
#include <iostream>
#include <utility>
#include <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. Сравнивайте пару в указанном порядке.