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

Для каждого из 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
Разбор примера по шагам
ТребованиеВыбранная модельПричина
49 за 7Дешевле точного совпадения; мощнее при равной цене
89 за 7Дешевле модели 8 за 9
1012 за 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))
#include <algorithm>
#include <iostream>
#include <utility>
#include <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 выбрал бы меньшую мощность. Минус перед мощностью задаёт нужный второй критерий.

  • Убрать купленную модель

    Количество экземпляров неограниченно. Одну лучшую модель можно купить для многих участков.